Merge Sorted Array
Asked at Google, Amazon, Microsoft, Oracle
Problem
Given two sorted arrays nums1 and nums2, merge nums2 into nums1 in-place. nums1 has a length of m + n, with the first m elements being the actual values and the rest being placeholders. This problem tests your ability to merge from the end to avoid overwriting elements.
Asked At
| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Amazon | Easy | View all Amazon questions → |
| Microsoft | Easy | View all Microsoft questions → |
| Oracle | Easy | View all Oracle questions → |
How to Think About It
Brute force: merge both arrays into a new array, sort it, copy back. That's O((m+n) log(m+n)) -- you lose the fact that both arrays are already sorted.
Better approach: use two pointers starting from the beginning. Compare elements and copy the smaller one to a temporary array. Then copy back. That's O(m+n) time but O(m+n) extra space.
Key insight: fill nums1 from the END. Start comparing from the last elements of both arrays. The largest element goes to position m+n-1. This way, you never overwrite elements you haven't read yet.
Why from the end: nums1 has extra space at the end (indices m to m+n-1). By filling from the back, you use that empty space. If you fill from the front, you'd overwrite nums1 elements before reading them.
Visual walkthrough: nums1 = [1,2,3,0,0,0], m=3, nums2 = [2,5,6], n=3
Pointers: p1=2 (nums1 last real), p2=2 (nums2 last), write=5 (nums1 last slot)
- nums1[2]=3 > nums2[2]=6? No. nums1[5]=6. p2=1, write=4.
- nums1[2]=3 > nums2[1]=5? No. nums1[4]=5. p2=0, write=3.
- nums1[2]=3 > nums2[0]=2? Yes. nums1[3]=3. p1=1, write=2.
- nums1[1]=2 > nums2[0]=2? No. nums1[2]=2. p2=-1, write=1.
- p2 < 0, done. nums1[0:3] remaining = [1,2]. Copy remaining from nums1.
Result: [1,2,2,3,5,6]
Edge cases: nums2 is empty (nothing to merge). nums1 is empty (just copy nums2). All elements in nums2 are smaller (nums1 shifts right). All elements in nums2 are larger (appended at end).
Optimal Approach
Step 1: Initialize three pointers: p1 = m-1, p2 = n-1, write = m+n-1.
Step 2: While p1 >= 0 and p2 >= 0:
- If nums1[p1] > nums2[p2], set nums1[write] = nums1[p1], decrement p1
- Otherwise, set nums1[write] = nums2[p2], decrement p2
- Decrement write
Step 3: If p2 >= 0 (nums2 has remaining elements), copy them to nums1[0..p2].
Step 4: If p1 >= 0 (nums1 has remaining elements), they're already in place.
Walkthrough for nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3:
- p1=2, p2=2, write=5
- nums1[2]=3 < nums2[2]=6: nums1[5]=6, p2=1, write=4
- nums1[2]=3 < nums2[1]=5: nums1[4]=5, p2=0, write=3
- nums1[2]=3 > nums2[0]=2: nums1[3]=3, p1=1, write=2
- nums1[1]=2 == nums2[0]=2: nums1[2]=2, p2=-1, write=1
- p2 < 0, done. nums1[0..1] = [1,2] already in place.
- Result: [1,2,2,3,5,6]
Time: O(m+n) -- each element is moved at most once. Space: O(1) -- in-place merge.
What Trips People Up in Real Interviews
Merging from the front instead of the back. If you start from index 0, you overwrite nums1 elements before reading them. Always merge from the end using write = m + n - 1.
Forgetting to copy remaining nums2 elements after the main loop. When p1 runs out but p2 still has elements, those must be copied into nums1[0..p2]. Remaining nums1 elements are already in place.
Not initializing p1, p2, and write correctly. p1 = m - 1 (last real element of nums1), p2 = n - 1 (last element of nums2), write = m + n - 1 (last slot). Off-by-one here breaks everything.
Confusing this with merge two sorted arrays into a new array. This problem requires in-place merging with no extra space, which is why the reverse traversal is essential.
Using a two-pointer approach from the front with a temporary array. While that works in O(m+n) time, it uses O(m+n) extra space. The interviewer expects the O(1) space reverse-merge solution.
Solution Code
def merge(nums1, m, nums2, n):
p1, p2, write = m - 1, n - 1, m + n - 1
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[write] = nums1[p1]
p1 -= 1
else:
nums1[write] = nums2[p2]
p2 -= 1
write -= 1
while p2 >= 0:
nums1[write] = nums2[p2]
p2 -= 1
write -= 1Frequently Asked Questions
What is the Merge Sorted Array problem?
Given two sorted arrays nums1 and nums2, merge nums2 into nums1 in-place. nums1 has a length of m + n, with the first m elements being the actual values and the rest being placeholders. This problem tests your ability to merge from the end to avoid overwriting elements.
How do you solve Merge Sorted Array?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Merge Sorted Array?
Merge Sorted Array is asked at Google, Amazon, Microsoft, Oracle. It is a easy difficulty problem.
What are common mistakes on Merge Sorted Array?
- Merging from the front instead of the back. If you start from index 0, you overwrite `nums1` elements before reading them. Always merge from the end using `write = m + n - 1`.
- Forgetting to copy remaining `nums2` elements after the main loop. When `p1` runs out but `p2` still has elements, those must be copied into `nums1[0..p2]`. Remaining `nums1` elements are already in place.
- Not initializing `p1`, `p2`, and `write` correctly. `p1 = m - 1` (last real element of `nums1`), `p2 = n - 1` (last element of `nums2`), `write = m + n - 1` (last slot). Off-by-one here breaks everything.
- Confusing this with merge two sorted arrays into a new array. This problem requires in-place merging with no extra space, which is why the reverse traversal is essential.
- Using a two-pointer approach from the front with a temporary array. While that works in `O(m+n)` time, it uses `O(m+n)` extra space. The interviewer expects the `O(1)` space reverse-merge solution.