Merge Sorted Array

Difficulty: Easy

Problem

Two integer arrays nums1 and nums2 are each sorted in non-decreasing order, holding m and n real values respectively. nums1 has room for m + n entries: its first m are real values and its last n are placeholder zeros. Fold nums2 into nums1 so that nums1 ends up fully sorted, modifying nums1 in place.

Example

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The real values are [1,2,3] in nums1 and [2,5,6] in nums2. Placed together in order they form [1,2,2,3,5,6], which is stored in nums1.

Brute-force approach

Copy nums2 into the end of nums1, then sort the entire array.

Steps

  1. Copy all elements of nums2 into the back of nums1
  2. Sort the entire nums1 array

Time complexity: O((m+n) log(m+n)) · Space complexity: O(1)

Trade-offs

  • Sorting is O((m+n) log(m+n)) when we can do O(m+n)
  • Doesn't take advantage of the fact that both arrays are already sorted

Optimal approach

Key insight: By filling from the back, we never overwrite unprocessed elements. The largest of the two current elements goes to position p.

Use three pointers starting from the end. Compare the largest remaining elements and place them at the back of nums1.

Steps

  1. Initialize p1 = m-1, p2 = n-1, p = m+n-1
  2. While both p1 and p2 are valid, place the larger at position p
  3. Decrement p and the pointer of the chosen element
  4. If p2 still has elements, copy them

Time complexity: O(m + n) · Space complexity: O(1)

Pseudocode

function merge(nums1, m, nums2, n):
    p1 = m - 1
    p2 = n - 1
    p = m + n - 1
    
    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1
    
    while p2 >= 0:
        nums1[p] = nums2[p2]
        p2 -= 1
        p -= 1

Hints

  • Start from the END of both arrays to avoid overwriting elements
  • Use three pointers: p1 at end of nums1 valid elements, p2 at end of nums2, p at end of nums1 total
  • The larger element goes to position p first

Check your understanding of Merge Sorted Array

Why do we start merging from the end instead of the beginning?

Starting from the beginning would overwrite elements in nums1 that we haven't processed yet. If we start from the front and place smaller elements first, we'd overwrite elements in nums1 that we still need. Starting from the back avoids this because we're filling empty positions (the trailing zeros).

What happens if p2 still has elements left but p1 is exhausted?

We copy remaining nums2 elements into nums1. If p1 is exhausted but p2 isn't, remaining nums2 elements are all smaller than what's already placed. We copy them into the front of nums1.

Related problems

Keep practising