How to Merge Two Sorted Arrays In‑Place Without Extra Space

Introduction: The interviewer asks to merge two non‑decreasing integer arrays nums1 and nums2, where nums1 has length m+n with the last n positions set to 0.

Problem Statement

Given nums1, m, nums2, n, merge nums2 into nums1 so that the final array remains sorted in non‑decreasing order. The result must be stored in nums1, not returned.

Naïve Solution

A straightforward approach creates a new array sorted of size m+n, uses two pointers to compare elements, fills sorted, then copies it back to nums1. The time complexity is O(m+n) and the extra space is O(m+n).

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = 0, p2 = 0;
    int[] sorted = new int[m + n];
    int cur;
    while (p1 < m || p2 < n) {
        if (p1 == m) {
            cur = nums2[p2++];
        } else if (p2 == n) {
            cur = nums1[p1++];
        } else if (nums1[p1] < nums2[p2]) {
            cur = nums1[p1++];
        } else {
            cur = nums2[p2++];
        }
        sorted[p1 + p2 - 1] = cur;
    }
    for (int i = 0; i < m + n; i++) {
        nums1[i] = sorted[i];
    }
}

The interviewer asks to explain the line sorted[p1 + p2 - 1] = cur, which uses the sum of the two pointers (minus one) as the current index in the temporary array.

In‑Place Solution

To avoid extra space, we work directly on nums1 using three pointers: p1 at the last valid element of the original part of nums1, p2 at the last element of nums2, and p3 at the last position of the merged array.

We compare the elements from the end, placing the larger one at nums1[p3] and moving the corresponding pointers backward.

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1; // last element of the original nums1
    int p2 = n - 1; // last element of nums2
    int p3 = m + n - 1; // last position of merged array

    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p3--] = nums1[p1--];
        } else {
            nums1[p3--] = nums2[p2--];
        }
    }
    while (p2 >= 0) {
        nums1[p3--] = nums2[p2--];
    }
}

This algorithm runs in O(m+n) time and uses O(1) extra space, meeting the interviewer's requirement.