#88 Merge Sorted Array
the problem
In plain words
nums1 has room for m + n numbers: its first m values are sorted and its last n slots are free (they hold 0). nums2 holds n sorted numbers. Merge nums2 into nums1 so that all m + n numbers end up sorted in nums1. Return nothing.
in nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
out [1,2,2,3,5,6]
in nums1 = [1], m = 1, nums2 = [], n = 0
out [1]
in nums1 = [0], m = 0, nums2 = [1], n = 1
out [1]
m = 0, so the 0 in nums1 is only a free slot.
- 0 ≤ m, n ≤ 200
- 1 ≤ m + n ≤ 200
- -10⁹ ≤ values ≤ 10⁹
- Follow-up: O(m + n) time
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTwo pointers (one per sequence)Merge sort & merging sorted runs
where this runsJava's TimSort (Arrays.sort on objects, Collections.sort) merges sorted runs in place; when the right run is the shorter one, its mergeHi copies that run aside and fills from the back — this exact move.
The free space is at the back of nums1, so fill it from the back: the larger of the two last values goes into the last slot. Writing backwards never overwrites a value you still need.
solutions
From brute force to optimal
Put nums2 into the free tail and sort the whole array.
- System.arraycopy(nums2, 0, nums1, m, n).
- Arrays.sort(nums1).
The sort ignores that both parts were already sorted.
The dual-pivot quicksort's recursion stack.
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { System.arraycopy(nums2, 0, nums1, m, n); // fill the empty tail Arrays.sort(nums1); // ignores that both halves were already sorted }}Save nums1's values aside, then do the classic take-the-smaller merge into nums1.
- first = copy of nums1[0..m).
- Take the smaller of first[i] and nums2[j] into nums1[k++].
- Copy whatever is left.
Each value is copied once.
The saved copy of nums1.
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int[] first = Arrays.copyOf(nums1, m); // save nums1's values before overwriting them int i = 0, j = 0, k = 0; while (i < m && j < n) nums1[k++] = first[i] <= nums2[j] ? first[i++] : nums2[j++]; while (i < m) nums1[k++] = first[i++]; while (j < n) nums1[k++] = nums2[j++]; }}i and j at the last real values, k at the last slot; the bigger value goes to k.
- i = m − 1, j = n − 1, k = m + n − 1.
- While j ≥ 0: if i ≥ 0 and nums1[i] > nums2[j], nums1[k--] = nums1[i--]; else nums1[k--] = nums2[j--].
- When nums2 runs out, nums1's remaining values are already in place.
Every step fills one slot for good.
Three indices.
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int i = m - 1, j = n - 1, k = m + n - 1; // last value of each, last free slot while (j >= 0) { // nums2 empty → the rest of nums1 is already in place if (i >= 0 && nums1[i] > nums2[j]) { nums1[k--] = nums1[i--]; // nums1 holds the bigger value } else { nums1[k--] = nums2[j--]; // nums2's value is bigger or equal, or nums1 is used up } } }}Dry run
in the room
How to say it in the interview
talk track
- Point out where the free space is — that's the whole trick.
- Explain why the loop runs only while j ≥ 0: leftover nums1 values are already sorted and in place.
- Prove nothing is overwritten: k = i + j + 1, so while j ≥ 0 the write slot is always to the right of i.
traps
- Merging from the front in place: you overwrite nums1 values before reading them.
- Testing
nums1[i] > nums2[j]without checkingi >= 0first: once nums1 runs out,nums1[-1]throwsArrayIndexOutOfBoundsException.
what they ask next
Follow-ups
Merge Two Sorted Lists (LC 21)?
Same take-the-smaller loop, but you relink nodes instead of copying values. No free-space problem, so go front to back.
Merge k sorted arrays?
Put each array's current head in a min-heap (PriorityQueue) and pop the smallest: O(N log k) for N values in total.
before you submit
Edge cases to test
- n = 0: nothing to do.
- m = 0: copy all of nums2 — the zeros in nums1 are free slots, not values.
- Every nums2 value smaller than every nums1 value: nums1's values all slide to the back.
- Equal values across the arrays, and extremes like ±10⁹: compare, never subtract.
practise next
Similar problems
- #21Merge Two Sorted ListsEasyin Linked Lists
- #977Squares of a Sorted ArrayEasyin Two Pointers
- #23Merge k Sorted ListsHardin Heaps
- #4Median of Two Sorted ArraysHardin Binary Search