Merge Sorted Array
Merge Sorted Array is a easy arrays & hashing problem solved with the two pointer pattern.
The best approach, optimal (three pointers from the back), runs in O(m + n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (copy, then sort) up.
Problem
You get two integer arrays sorted in non-decreasing order: nums1, whose first m values are real and whose last n slots are placeholder zeros, and nums2, which holds n values.
Merge nums2 into nums1 so that all m + n slots of nums1 hold the combined values in sorted order. Do it in place: the function returns nothing, and the result is read from nums1 afterwards.
Examples
Example 1
- Input
nums1 = [2, 5, 9, 0, 0], m = 3, nums2 = [4, 10], n = 2- Output
[2, 4, 5, 9, 10]- Why
- The three real values of nums1 and the two of nums2 are merged into the five slots of nums1.
Example 2
- Input
nums1 = [0, 0, 0], m = 0, nums2 = [-3, 1, 1], n = 3- Output
[-3, 1, 1]- Why
- nums1 has no real values yet, so the result is just nums2.
Example 3
- Input
nums1 = [7], m = 1, nums2 = [], n = 0- Output
[7]- Why
- Nothing to merge: nums1 stays as it is.
Constraints
nums1.length == m + n,nums2.length == n0 <= m, n <= 200,1 <= m + n <= 200-10^9 <= nums1[i], nums2[j] <= 10^9- The first
mvalues ofnums1and all ofnums2are sorted in non-decreasing order.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (copy, then sort) | O((m + n) log(m + n)) | O(log(m + n)) |
| Optimal (three pointers from the back) | O(m + n) | O(1) |
1Brute force (copy, then sort)
O((m + n) log(m + n))Sorting dominates.O(log(m + n))Only the sort's internal stack.Copy nums2 into the free tail of nums1 and sort the whole array. Simple, but it ignores that both halves are already sorted.
- For j from 0 to n - 1: nums1[m + j] = nums2[j].
- Sort nums1.
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for (int j = 0; j < n; j++) {
nums1[m + j] = nums2[j];
}
Arrays.sort(nums1);
}
}class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
for j in range(n):
nums1[m + j] = nums2[j]
nums1.sort()class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
for (int j = 0; j < n; j++) {
nums1[m + j] = nums2[j];
}
sort(nums1.begin(), nums1.end());
}
};function merge(nums1, m, nums2, n) {
for (let j = 0; j < n; j++) {
nums1[m + j] = nums2[j];
}
nums1.sort((a, b) => a - b);
}2Optimal (three pointers from the back)
O(m + n)Each slot of nums1 is written once.O(1)Three index variables.Walk both arrays from their last real value and fill nums1 from its last slot. The larger of the two current values goes into the current slot. The write position is always at or after the nums1 read position, so no unread value is overwritten.
- i = m - 1, j = n - 1, k = m + n - 1.
- While j >= 0: if i >= 0 and nums1[i] > nums2[j], set nums1[k] = nums1[i] and i--; otherwise nums1[k] = nums2[j] and j--. Then k--.
- When nums2 is exhausted, the remaining nums1[0..i] are already in their final places.
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
}
}class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
i, j, k = m - 1, n - 1, m + n - 1
while j >= 0:
if i >= 0 and nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
}
};function merge(nums1, m, nums2, n) {
let i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) {
nums1[k--] = nums1[i--];
} else {
nums1[k--] = nums2[j--];
}
}
}Edge cases to test
- m = 0: copy all of nums2
- n = 0: nothing changes
- Every value of nums2 is smaller than every value of nums1
- Equal values in both arrays
- The padding zeros of nums1 are not real values and must not leak into the answer
Hints
Hint 1
Merging from the front would overwrite values of nums1 you still need. Where is there free space?
Hint 2
The free slots are at the end. Fill nums1 from the back, always placing the larger of the two current last values.
Hint 3
Once nums2 is used up, the remaining nums1 values are already in place.
FAQ
What is the best time complexity for Merge Sorted Array?
Optimal (three pointers from the back) runs in O(m + n) time and O(1) extra space. Each slot of nums1 is written once.
Which pattern does Merge Sorted Array use?
It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.
Is there a brute force solution for Merge Sorted Array?
Yes. Brute force (copy, then sort) takes O((m + n) log(m + n)) time and O(log(m + n)) space. Copy nums2 into the free tail of nums1 and sort the whole array.
Which edge cases should I test for Merge Sorted Array?
m = 0: copy all of nums2; n = 0: nothing changes; Every value of nums2 is smaller than every value of nums1; Equal values in both arrays; The padding zeros of nums1 are not real values and must not leak into the answer.