Merge Sorted Array

easy array two pointers in-place

Problem

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. The number of elements initialized in nums1 and nums2 are m and n respectively.

Inputnums1 = [1, 3, 5, 0, 0, 0], m = 3, nums2 = [2, 4, 6], n = 3

Output[1, 2, 3, 4, 5, 6]

Three pointers walk leftward: i at the end of nums1's real data, j at the end of nums2, k at the end of nums1's full length.

nums1 real values (sorted, comma-separated)

nums2 (sorted, comma-separated)

def merge(nums1, m, nums2, n):
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[k] = nums1[i]
            i -= 1
        else:
            nums1[k] = nums2[j]
            j -= 1
        k -= 1

function merge(nums1, m, nums2, n) {
  let i = m - 1, j = n - 1, k = m + n - 1;
  while (j >= 0) {
    if (i >= 0 && nums1[i] > nums2[j]) {
      nums1[k--] = nums1[i--];
    } else {
      nums1[k--] = nums2[j--];
    }
  }
}

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }
}

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int i = m - 1, j = n - 1, k = m + n - 1;
    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) {
            nums1[k--] = nums1[i--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
}

Explanation

The clever trick here is to fill nums1 from the back instead of the front. The back of nums1 is empty (those trailing zeros), so we can drop the largest values there without ever overwriting data we still need.

We use three pointers: i at the last real value of nums1, j at the last value of nums2, and k at the very last slot of nums1. At each step we compare nums1[i] and nums2[j] and write the bigger one into slot k, then step that pointer and k leftward.

The loop runs while j >= 0. Once nums2 is fully placed, any remaining nums1 values are already sitting in the right spot, so we're done.

Example: nums1 = [1,3,5,0,0,0], nums2 = [2,4,6]. Compare 5 and 6: 6 is bigger, write it last. Then 5 vs 4: write 5. Then 3 vs 4: write 4, and so on.

Filling from the right gives [1,2,3,4,5,6] in place, with no extra array and no risk of clobbering values we still need.

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