Merge Sorted Array

Difficulty: Easy

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. The final sorted array should be stored inside nums1. nums1 has a length of m + n, where the last n elements are set to 0 and should be ignored.

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 arrays we are merging are [1,2,3] and [2,5,6]. The result of the merge is [1,2,2,3,5,6].

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)