Merge Two Sorted Arrays Into the First Array In Place
Solve this Problemnums1 and nums2, and two counts m and n telling you how many real values sit at the front of each. nums1 is deliberately longer than its real content — it has exactly n extra slots at the end, reserved so nums2's values can be folded straight into it.
Merge nums2 into nums1 so that the first m + n positions hold every value from both arrays in non-decreasing order. Try to avoid allocating a second array the size of the result — filling nums1 from the back, largest values first, means you never overwrite a value before you've had a chance to read it.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ m, n ≤ 200 - ◆
nums1.length == m + n - ◆
nums2.length == n - ◆
-10⁹ ≤ nums1[i], nums2[j] ≤ 10⁹ - ◆
Both nums1's first m entries and all of nums2 are sorted in non-decreasing order
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
| 1 | class Solution { |
| 2 | public int[] mergeSortedArrays(int[] nums1, int m, int[] nums2, int n) { |
| 3 | int p1 = m - 1; |
| 4 | int p2 = n - 1; |
| 5 | int write = m + n - 1; |
| 6 | while (p2 >= 0) { |
| 7 | if (p1 >= 0 && nums1[p1] > nums2[p2]) { |
| 8 | nums1[write--] = nums1[p1--]; |
| 9 | } else { |
| 10 | nums1[write--] = nums2[p2--]; |
| 11 | } |
| 12 | } |
| 13 | return nums1; |
| 14 | } |
| 15 | } |
| 16 |
33225nums1 has 3 real values up front ([1, 4, 7]) and 3 filler zero slots at the back, reserved for merging nums2 in. p1=2 marks the last real value in nums1, p2=2 marks the last value in nums2, and write=5 marks the last slot we'll fill.
Approach & Solutions
Brute Force — Copy and Sort
BruteCopy nums1's first m real values together with all of nums2 into a fresh array, then sort that array from scratch. It works, but it throws away the fact that both halves were already sorted — a full sort is more work than this problem needs.
O((m+n) log(m+n))O(m+n)1class Solution {
2 public int[] mergeSortedArrays(int[] nums1, int m, int[] nums2, int n) {
3 int[] result = new int[m + n];
4 for (int i = 0; i < m; i++) result[i] = nums1[i];
5 for (int i = 0; i < n; i++) result[m + i] = nums2[i];
6 Arrays.sort(result);
7 return result;
8 }
9}Better — Merge Into New Array
BetterMerge the two sorted runs the classic merge-sort way: walk pointers i (through nums1's first m real values) and j (through nums2), repeatedly taking whichever front value is smaller into a fresh result array. Once one side runs out, copy over whatever's left of the other. This reaches the same O(m+n) time as the optimal approach below, but it needs a separate result array — filling nums1 from the back instead achieves the same speed truly in-place.
O(m+n)O(m+n)1class Solution {
2 public int[] mergeSortedArrays(int[] nums1, int m, int[] nums2, int n) {
3 int[] result = new int[m + n];
4 int i = 0, j = 0, k = 0;
5 while (i < m && j < n) {
6 if (nums1[i] <= nums2[j]) {
7 result[k++] = nums1[i++];
8 } else {
9 result[k++] = nums2[j++];
10 }
11 }
12 while (i < m) result[k++] = nums1[i++];
13 while (j < n) result[k++] = nums2[j++];
14 return result;
15 }
16}Optimal — Three Pointers From the Back
OptimalFill nums1 starting from its very last slot, working backwards. Compare the largest remaining candidate from each array's unread portion and place whichever is bigger. Writing from the back means you only ever overwrite slots you've already used or that were empty filler — you never clobber a nums1 value before reading it. Once nums2 runs out, whatever's left at the front of nums1 was already smaller than everything placed, so it needs no more work.
O(m+n)O(1) extra1class Solution {
2 public int[] mergeSortedArrays(int[] nums1, int m, int[] nums2, int n) {
3 int p1 = m - 1;
4 int p2 = n - 1;
5 int write = m + n - 1;
6 while (p2 >= 0) {
7 if (p1 >= 0 && nums1[p1] > nums2[p2]) {
8 nums1[write--] = nums1[p1--];
9 } else {
10 nums1[write--] = nums2[p2--];
11 }
12 }
13 return nums1;
14 }
15}