Two already-sorted invoice batches have to land in one buffer. nums1 is that buffer: m live amounts, then n empty slots reserved for nums2. The intern copied both into a new list and called Arrays.sort. A few hundred invoices were fine. The board then forbade the extra array and forbade the sort: both inputs are already ordered; fold them into nums1 without losing a value you have not written yet.

Merge Sorted Array asks you to fold nums2 into nums1 in place. An array already gives nums1[i] for free. Copying then sorting uses that and throws away the order you were given. Writing from index 0 overwrites a live nums1 head before you have compared it.

This is an interview writeup, not a two-pointers lecture. The two pointers post owns the two-sequence merge into a third buffer. Here the unused tail is already empty, so the write starts there and unread heads stay intact.

The problem

Given an int[] nums1 of length m + n whose first m slots are sorted values and whose last n slots are unused padding, and an int[] nums2 of n sorted values, write the merged sorted sequence into nums1. Mutate nums1. Do not allocate a second array of m + n.

nums1 = [1, 3, 8, 0, 0, 0], m = 3
nums2 = [4, 6, 9],           n = 3
→  [1, 3, 4, 6, 8, 9]

nums1 = [5], m = 1
nums2 = [],  n = 0
→  [5]

nums1 = [0, 0], m = 0
nums2 = [3, 8], n = 2
→  [3, 8]

Note: The padding zeros are unused, not data. A real 0 can still sit in the live prefix of nums1; m tells you how many slots count. Writing from the front of nums1 clobbers a live head you still need to compare.

Copy into the pad, then sort — or merge into extra memory

Drop nums2 onto the unused tail and sort the whole buffer. Correct. You paid O((m + n) log (m + n)) after both files arrived already sorted. An extra array of m + n with a two-pointer merge is also correct and still the extra buffer they forbade.

void mergeCopyAndSort(int[] nums1, int m, int[] nums2, int n) {
    for (int j = 0; j < n; j++) {
        nums1[m + j] = nums2[j];
    }
    Arrays.sort(nums1);
}

At n = 20 this is a rounding error. The complaint is the sort, and the extra array. The unused tail is already empty, so a backwards write answers: which tail is larger?

Three pointers: fill from the back

i walks the live tail of nums1 (m - 1). j walks the tail of nums2 (n - 1). w is the next write slot in nums1 (m + n - 1). Each step writes the larger of nums1[i] and nums2[j] into w, then steps that tail and w. Stop when nums2 is exhausted: leftover nums1 values already sit in the right slots.

nums1 = [1, 3, 8, 0, 0, 0]   nums2 = [4, 6, 9]
i=2  j=2  w=5

9 > 8  write 9 at w     [1, 3, 8, 0, 0, 9]   j=1  w=4
6 < 8  write 8 at w     [1, 3, 8, 0, 8, 9]   i=1  w=3
6 > 3  write 6 at w     [1, 3, 8, 6, 8, 9]   j=0  w=2
4 > 3  write 4 at w     [1, 3, 4, 6, 8, 9]   j=-1  stop

The Java is that walk:

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

Time is O(m + n) — each index is written once. Extra space is O(1) — three indexes. Copy-and-sort is the same extra space and a worse time bill; say so, then walk from the back when they want the merge you were given.

Note: Loop while j >= 0, not while w >= 0. When nums2 is gone, remaining nums1 values are already in place. The i >= 0 guard copies a leftover nums2 prefix after nums1’s live head is spent (m = 0 is that case). Equals can go either way; the else takes nums2.

What interviewers usually poke next

  • Why not write from the front. nums1[0] is live. A forward write overwrites it before the merge has compared it. The empty slots are at the far end, so the write starts there.
  • No padding, new result array. Then the extra buffer is the intended answer, not a cop-out. Two pointers from the heads, one write index.
  • m = 0 or n = 0. n = 0 never enters the loop. m = 0 copies all of nums2 backwards into nums1.
  • Linked lists instead of arrays. Different problem: you splice nodes, you do not have random write into padding. Do not start a list lecture unless they switch the prompt.

You are done with this problem when you can walk [1, 3, 8, 0, 0, 0] and [4, 6, 9] on a whiteboard from the back, and you can say out loud why copy-then-sort throws away the order, why a forward write clobbers unread heads, and why the loop stops when j is spent.