Merge Sorted Array

Easy

ArrayTwo PointersSorting

Problem Description

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 nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

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]
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].

Example 2:


Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:


Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1.

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

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Solution Approaches

Naive Approach: Merge and Sort

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

The simplest approach is to copy all elements from nums2 into the empty space of nums1, then sort the entire array.

Algorithm:

1. Copy all elements from nums2 to positions m through m+n-1 in nums1 2. Sort nums1 using a built-in sort function 3. Done!

Why This Works: - We have exactly n empty spaces at the end of nums1 - After copying, we have all elements in one array - Sorting puts them in the correct order

Drawbacks: - Doesn't take advantage of the fact that both arrays are already sorted - Sorting is O((m+n) log(m+n)), which is slower than necessary - Wastes the pre-sorted property of the input

Solution Code

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  // Copy all elements from nums2 to the end of nums1
  for (let i = 0; i < n; i++) {
    nums1[m + i] = nums2[i];
  }

  // Sort the entire array
  nums1.sort((a, b) => a - b);
}

// Time: O((m+n) log(m+n)) due to sorting
// Space: O(1) if we don't count the space used by the sort algorithm

Visualization: MergeSortedNaiveViz(Component registered but not yet implemented)

Better Approach: Merge Forward (Extra Space)

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

Since both arrays are already sorted, we can use the classic merge operation from merge sort. However, if we merge forward (left to right), we'd overwrite elements in nums1 that we haven't processed yet.

Solution: Use a temporary array to store the result, then copy back.

Algorithm:

1. Create a temporary array result of size m + n 2. Use three pointers: - p1 = 0 for nums1 - p2 = 0 for nums2 - p = 0 for result 3. While both arrays have elements: - Compare nums1[p1] with nums2[p2] - Place the smaller one in result[p] - Increment the corresponding pointer 4. Copy remaining elements (if any) from nums1 or nums2 5. Copy result back to nums1

Why This Works: - We compare elements from the front of both sorted arrays - Always pick the smallest available element - This maintains sorted order in the result

Solution Code

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  const result: number[] = new Array(m + n);
  let p1 = 0; // Pointer for nums1
  let p2 = 0; // Pointer for nums2
  let p = 0;  // Pointer for result

  // Merge while both arrays have elements
  while (p1 < m && p2 < n) {
    if (nums1[p1] <= nums2[p2]) {
      result[p++] = nums1[p1++];
    } else {
      result[p++] = nums2[p2++];
    }
  }

  // Copy remaining elements from nums1 (if any)
  while (p1 < m) {
    result[p++] = nums1[p1++];
  }

  // Copy remaining elements from nums2 (if any)
  while (p2 < n) {
    result[p++] = nums2[p2++];
  }

  // Copy result back to nums1
  for (let i = 0; i < m + n; i++) {
    nums1[i] = result[i];
  }
}

Visualization: MergeSortedForwardViz(Component registered but not yet implemented)

Optimal Solution: Merge Backward (In-Place)

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

The key insight is to merge from right to left instead of left to right. This way, we fill the empty spaces at the end of nums1 without overwriting unprocessed elements.

Key Insight:

- nums1 has exactly n empty spaces at the end - If we start from the largest elements and work backwards, we'll fill these empty spaces first - We never overwrite elements we haven't processed yet!

Algorithm: 1. Initialize three pointers at the END of their respective ranges: - p1 = m - 1 (last element in nums1's valid range) - p2 = n - 1 (last element in nums2) - p = m + n - 1 (last position in nums1) 2. While p2 >= 0 (still have elements from nums2 to merge): - If p1 >= 0 and nums1[p1] > nums2[p2]: - nums1[p] = nums1[p1], decrement p1 and p - Else: - nums1[p] = nums2[p2], decrement p2 and p 3. Done! (If p2 < 0, remaining nums1 elements are already in place)

Why We Check p2 >= 0: - Once all nums2 elements are placed, any remaining nums1 elements are already in their correct positions - We don't need to move them

Example Walkthrough: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 - Initial: p1=2, p2=2, p=5 - Compare nums1[2]=3 vs nums2[2]=6 → 6 is larger → nums1[5]=6, p2=1, p=4 - Compare nums1[2]=3 vs nums2[1]=5 → 5 is larger → nums1[4]=5, p2=0, p=3 - Compare nums1[2]=3 vs nums2[0]=2 → 3 is larger → nums1[3]=3, p1=1, p=2 - Compare nums1[1]=2 vs nums2[0]=2 → equal, take nums2 → nums1[2]=2, p2=-1, p=1 - p2 < 0, stop. Result: [1,2,2,3,5,6]

Solution Code

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  // Start from the end of each array
  let p1 = m - 1;     // Last element in nums1's valid range
  let p2 = n - 1;     // Last element in nums2
  let p = m + n - 1;  // Last position in nums1

  // Merge from right to left
  while (p2 >= 0) {
    // If nums1 still has elements and its current element is larger
    if (p1 >= 0 && nums1[p1] > nums2[p2]) {
      nums1[p] = nums1[p1];
      p1--;
    } else {
      // Either nums1 is exhausted, or nums2's element is larger/equal
      nums1[p] = nums2[p2];
      p2--;
    }
    p--;
  }

  // No need to copy remaining nums1 elements - they're already in place
}

Visualization: MergeSortedBackwardViz(Component registered but not yet implemented)

Why Backward Merging Works

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

The backward merging approach is elegant because it exploits the structure of the problem:

The Problem Structure:

- nums1 has length m + n with the last n positions being empty (zeros) - We need to place m + n elements total - Both input arrays are sorted

The Insight: When merging forward (left to right), we face a conflict: - We want to write the smallest elements at the beginning of nums1 - But nums1 also contains elements we need to read from the beginning - This creates a read-write conflict that requires extra space

When merging backward (right to left), we have a perfect fit: - We want to write the largest elements at the end of nums1 - The end of nums1 is currently empty (filled with zeros) - There's no conflict! We can write to positions we don't need to read from

Visual Representation:


nums1 = [1, 2, 3, _, _, _]  m=3, n=3
         ↑           ↑
       (read)     (write)Forward: Read and write pointers collide!
Backward: Empty space provides room without conflicts

Proof of Correctness: At each step, we place the largest unplaced element in the rightmost unfilled position. This maintains the sorted order from right to left. Once all nums2 elements are placed, any remaining nums1 elements are already in their correct positions because: 1. They're smaller than all elements we've already placed (to their right) 2. They're already in sorted order 3. They're already in their final positions

This is why we only need to check p2 >= 0 in the loop condition—once nums2 is empty, we're done!

Solution Code

// Annotated solution showing the key insight
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  let p1 = m - 1;       // Reading from nums1 (right to left)
  let p2 = n - 1;       // Reading from nums2 (right to left)
  let p = m + n - 1;    // Writing to nums1 (right to left)

  // Critical insight: we write to empty space first!
  // The first n writes go to the empty positions [m, m+1, ..., m+n-1]
  // By the time we reach position m-1, we've consumed elements from that position

  while (p2 >= 0) {
    if (p1 >= 0 && nums1[p1] > nums2[p2]) {
      nums1[p--] = nums1[p1--];  // Move from nums1
    } else {
      nums1[p--] = nums2[p2--];  // Move from nums2
    }
  }

  // When p2 < 0: all nums2 elements are placed
  // Remaining nums1 elements are already in correct positions
}

// Why this is optimal:
// - Time: O(m + n) - single pass through both arrays
// - Space: O(1) - only three integer pointers
// - In-place: utilizes existing empty space in nums1

Visualization: MergeSortedInsightViz(Component registered but not yet implemented)