Merge Sorted Array

EASY✓ CHIP-TIMEDLC #88 — FULL STATEMENT ↗

The drill: Fold a second sorted array into the tail padding of the first so a single fully sorted run remains. The slack sits at the back of the array — which is the loudest possible hint about which end to merge from.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

Two arrays arrive already sorted on their own: the first one is padded with extra empty slots at its tail, exactly enough room to hold every element from the second array once merged.

The counts m and n say how many real values sit in the front of each array — everything after position m in the first array is just padding waiting to be overwritten, not real data.

The result has to land inside that first array itself, fully sorted, using no second array as scratch space. The second array's contents can be treated as consumed once merged in.

EX 01

nums1 = [2, 5, 9, 0, 0, 0] · m = 3 · nums2 = [1, 6, 8] · n = 3

→ [1, 2, 5, 6, 8, 9]

FULL INTERLEAVE

EX 02

nums1 = [1] · m = 1 · nums2 = [] · n = 0

→ [1]

NOTHING TO MERGE IN

EX 03

nums1 = [0] · m = 0 · nums2 = [4] · n = 1

→ [4]

FIRST RUN EMPTY — PADDING ONLY

first array's real length m and second array's length n each run up to a few hundred
the first array's real entries occupy only its first m slots, the rest is padding
both input runs already arrive individually sorted
the merge must happen inside the first array, no auxiliary array allowed

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Dumping the second array into the padding and sorting the whole thing works — but the sort throws away the one gift you were given: both runs already arrive ordered.

HINT 2 THE STRUCTURE

A forward merge keeps overwriting values of the first array that you still need to read. The empty slots live at the back — merge in the direction where you only ever pave over dead space.

HINT 3 ONE STEP FROM THE ANSWER

Three pointers from the rear: compare the largest unplaced element of each run, drop the winner into the last open slot, walk everything leftward. Any leftover second-array entries copy straight in.

COACH'S BOARD — THE PATTERN, STEP BY STEP

MERGE FROM THE BACKPATTERN · THREE POINTERS, BACKWARDnums1 = [2, 5, 9, 0, 0, 0], m = 3 · nums2 = [1, 6, 8], n = 3

STEP 1

Merge from the back: i at 2 (nums1's last real value, 9), j at 2 (nums2's last, 8), w at slot 5, the last open slot.

STEP 1 / 8 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/merge-sorted-array.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i, j, w = m - 1, n - 1, m + n - 1
        while j >= 0:  # once nums2 is spent, nums1's prefix is already in place
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[w] = nums1[i]
                i -= 1
            else:
                nums1[w] = nums2[j]
                j -= 1
            w -= 1

TIME O(M+N)SPACE O(1)PYTHON · RACE PACE · 11 LN

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1[m:] = nums2  # overwrite the padding with the second run
        nums1.sort()

TIME O((M+N) LOG (M+N))SPACE O(LOG (M+N))PYTHON · TRAINING PACE · 4 LN

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, w = m + n - 1;
        while (j >= 0) { // once nums2 is spent, nums1's prefix is already in place
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[w--] = nums1[i--];
            } else {
                nums1[w--] = nums2[j--];
            }
        }
    }
}

TIME O(M+N)SPACE O(1)JAVA · RACE PACE · 12 LN

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        System.arraycopy(nums2, 0, nums1, m, n); // overwrite the padding
        Arrays.sort(nums1);
    }
}

TIME O((M+N) LOG (M+N))SPACE O(LOG (M+N))JAVA · TRAINING PACE · 6 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED