Merge Sorted Array

Difficulty: Easy Source: NeetCode

Problem

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums2 into nums1 as one sorted array in-place. nums1 has length m + n; the last n positions are zeroed out as placeholders.

Example 1: Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]

Example 2: Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1]

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9

Prerequisites

Before attempting this problem, you should be comfortable with:

• Sorted Arrays — merging two sorted sequences (merge step from merge sort)
• Two Pointers — using multiple indices to avoid overwriting data you still need

1. Brute Force

Intuition

Copy all elements of nums2 into the trailing placeholder slots of nums1, then sort nums1. We’re throwing away the fact that both arrays are already sorted, but it gets the job done in a single sort call. The sort costs O((m+n) log(m+n)), which is fine for small inputs.

Algorithm

1. Copy nums2 into nums1[m:].
2. Sort nums1 in place.

Solution

def merge(nums1, m, nums2, n):
    for i in range(n):
        nums1[m + i] = nums2[i]
    nums1.sort()


nums1 = [1, 2, 3, 0, 0, 0]
merge(nums1, 3, [2, 5, 6], 3)
print(nums1)  # [1, 2, 2, 3, 5, 6]

nums1 = [1]
merge(nums1, 1, [], 0)
print(nums1)  # [1]

nums1 = [0]
merge(nums1, 0, [1], 1)
print(nums1)  # [1]

Complexity

• Time: O((m + n) log(m + n))
• Space: O(1) (in-place sort)

2. Three Pointers from the End

Intuition

If we merge from the front, we risk overwriting elements in nums1 that we still need. So instead, fill from the back. The largest unplaced element among both arrays belongs at the very end of nums1. Compare the last real elements of nums1 and nums2, write the bigger one to the current tail position, and move that pointer backward. Repeat until we exhaust one or both arrays. If nums2 still has elements left when nums1 runs out, copy them in — if nums1 runs out first, its remaining elements are already in place.

Algorithm

1. Initialize p1 = m - 1, p2 = n - 1, tail = m + n - 1.
2. While p1 >= 0 and p2 >= 0:
   • If nums1[p1] >= nums2[p2]: write nums1[p1] to nums1[tail], decrement p1.
   • Else: write nums2[p2] to nums1[tail], decrement p2.
   • Decrement tail.
3. While p2 >= 0: write nums2[p2] to nums1[tail], decrement both p2 and tail.
4. (If p1 >= 0, those elements are already in the correct positions — no action needed.)

Solution

def merge(nums1, m, nums2, n):
    p1 = m - 1
    p2 = n - 1
    tail = m + n - 1

    while p1 >= 0 and p2 >= 0:
        if nums1[p1] >= nums2[p2]:
            nums1[tail] = nums1[p1]
            p1 -= 1
        else:
            nums1[tail] = nums2[p2]
            p2 -= 1
        tail -= 1

    # Any remaining elements in nums2 still need to be placed
    while p2 >= 0:
        nums1[tail] = nums2[p2]
        p2 -= 1
        tail -= 1


nums1 = [1, 2, 3, 0, 0, 0]
merge(nums1, 3, [2, 5, 6], 3)
print(nums1)  # [1, 2, 2, 3, 5, 6]

nums1 = [1]
merge(nums1, 1, [], 0)
print(nums1)  # [1]

nums1 = [0]
merge(nums1, 0, [1], 1)
print(nums1)  # [1]

Complexity

• Time: O(m + n)
• Space: O(1)

Common Pitfalls

Merging from the front and overwriting unread elements. If you start writing at index 0, you’ll clobber nums1 values that haven’t been compared yet. Always fill from the tail when merging in-place into nums1.

Forgetting the leftover nums2 elements. After the main loop, nums2 may still have elements smaller than everything remaining in nums1. The second while p2 >= 0 loop handles this. You don’t need a symmetric loop for p1 because those elements are already sitting in the right positions.

Starting tail at the wrong index. tail should start at m + n - 1, the last valid index of nums1. A common mistake is starting at m - 1 (the last real element), which leaves no room for nums2.