Sorting · 152Easy
Merge Sorted Array
You are given two sorted arrays nums1 (with m real values followed by n zeroes as spare room) and nums2 (with n values). Merge nums2 into nums1 IN PLACE so nums1 ends up sorted.
Constraints
- nums1.length == m + n, nums2.length == n
- 0 <= m, n <= 200
- -10^9 <= nums1[i], nums2[j] <= 10^9
Examples
merge([1,2,3,0,0,0], 3, [2,5,6], 3) -> [1,2,2,3,5,6] merge([1], 1, [], 0) -> [1] merge([0], 0, [1], 1) -> [1] // nums1 has no real values merge([4,5,6,0,0,0], 3, [1,2,3], 3) -> [1,2,3,4,5,6] // all of nums2 sorts first merge([1,2,2,0], 3, [2], 1) -> [1,2,2,2] // duplicates across both arrays merge([-1,3,0,0], 2, [-2,0], 2) -> [-2,-1,0,3] // negatives, and a real 0 in nums2
Edge cases
- m = 0 means nums1 holds only spare room.
- n = 0 leaves nums1 unchanged.
- FOLLOW-UP
- Can you come up with an algorithm that runs in O(m + n) time?
Show the target complexity (spoiler)
- Naive
- O((m + n) log(m + n)) time — concatenate then sort, throwing away the sorted
- Target
- O(m + n) time, O(1) space — fill from the BACK, comparing the tails of both arrays, so no unread value is ever overwritten.
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/20-sorting/152-merge-sorted-array.js ./practice c 152