Merge Two Sorted Arrays In Place

easy array two pointers in-place

Problem

Two non-decreasing arrays are given. The first one, nums1, has length m + n — its first m entries are real values and the last n are empty placeholder zeros reserved for the merge. The second, nums2, has length n. Merge nums2 into nums1 so the whole array ends up sorted, without allocating extra space. The trick: fill from the back. Both arrays' largest values sit at their right ends, so the largest remaining value goes into the rightmost empty slot, and there's no risk of overwriting a value we still need.

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--];
        }
    }
}

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