Merge two sorted arrays without extra space
Goldman SachsThe problem
Given two integer arrays **nums1 **and nums2. Both arrays are sorted in non-decreasing order.
Merge **both **the arrays into a **single **array **sorted **in non-decreasing order.
-
The **final **sorted array should be stored inside the array **nums1 **and it should be done in-place.
-
nums1 has a length of m + n, where the first m elements denote the elements of nums1 and rest are 0s.
-
**nums2 **has a length of n.
Input: nums1 = [-5, -2, 4, 5], nums2 = [-3, 1, 8] Output: [-5, -3, -2, 1, 4, 5, 8] Explanation: The merged array is: [-5, -3, -2, 1, 4, 5, 8], where [-5, -2, 4, 5] are from nums1 and [-3, 1, 8] are from nums2
Input: nums1 = [0, 2, 7, 8], nums2 = [-7, -3, -1] Output: [-7, -3, -1, 0, 2, 7, 8] Explanation: The merged array is: [-7, -3, -1, 0, 2, 7, 8], where [0, 2, 7, 8] are from nums1 and [-7, -3, -1] are from nums2
Input: nums1 = [1, 3, 5], nums2 = [2, 4, 6, 7]
- n == nums2.length.
- m + n == nums1.length.
- 0 <= n, m <= 1000
- -104 <= nums1[i], nums2[i] <= 104
- Both nums1 and nums2 are sorted in non-decreasing order.
cpp
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
}
};java
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
}
}python
class Solution:
def merge(self, nums1, m, nums2, n):javascript
class Solution {
merge(nums1, m, nums2, n) {
}
}csharp
public class Solution
{
public void Merge(IList<int> nums1, int m, IList<int> nums2, int n)
{
}
}go
func merge(nums1 []int, m int, nums2 []int, n int) {
}Stuck? Show a way to structure it+
- 01Set pointers at the last valid elements of both arrays and at nums1's final slot.
- 02Compare from the back and write the larger value into the write pointer.
- 03Move the corresponding pointer backward.
- 04Copy any remaining nums2 prefix; remaining nums1 values are already placed.
Reference answer
Then expect these follow-ups
How would you merge two arrays when neither has spare capacity?
Tests: space trade-offs
How would you merge k sorted arrays?
Tests: heap design
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question