Merge Sorted Array
EasyPrompt
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
Constraints:
nums1.length == m + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-109 <= nums1[i], nums2[j] <= 109
Follow up: Can you come up with an algorithm that runs in O(m + n) time?
Approaches
3 approaches with complexity analysis and trade-offs.
The most straightforward approach is to first merge the two arrays and then sort the resulting array. We can copy the elements of nums2 into the available space at the end of nums1 and then use a standard library sorting function to sort the entire nums1 array.
Algorithm
- Copy the
nelements fromnums2intonums1starting from indexm. - Use a standard sorting algorithm (like
Arrays.sort()in Java) to sort the firstm + nelements ofnums1.
Walkthrough
This method ignores the sorted nature of the input arrays. It first combines the two lists into one and then applies a general-purpose sorting algorithm.
- Copy
nums2: Thenelements ofnums2are copied to the end ofnums1, which hasnzero-padded slots available from indexmtom + n - 1. - Sort
nums1: After copying,nums1contains all the elements from both original arrays, but it is not sorted. A call to a standard sorting function, likejava.util.Arrays.sort(), is made to sort the entirenums1array of lengthm + n.
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { // Copy elements of nums2 into the end of nums1 for (int i = 0; i < n; i++) { nums1[m + i] = nums2[i]; } // Sort the entire nums1 array java.util.Arrays.sort(nums1); }}Complexity
Time
O((m+n) log(m+n))
Space
O(log(m+n)) to O(m+n)
Trade-offs
Pros
Simple to understand and implement.
Leverages highly optimized built-in sorting functions.
Cons
Inefficient as it doesn't utilize the fact that the input arrays are already sorted.
Time complexity is higher than the optimal solution.
A better approach is to use the fact that the arrays are sorted. We can iterate through both arrays using pointers and place the elements into a temporary array in sorted order. To perform this 'in-place' on nums1, we first need to copy the original m elements of nums1 to a separate array to avoid overwriting them during the merge process. Then, we merge the copied array and nums2 back into nums1.
Algorithm
- Create a copy of the first
melements ofnums1, let's call itnums1_copy. - Initialize three pointers:
p1fornums1_copy(starts at 0),p2fornums2(starts at 0), andpfornums1(starts at 0). - While
p1 < mandp2 < n:- Compare
nums1_copy[p1]andnums2[p2]. - Place the smaller element into
nums1[p]. - Increment the pointer of the array from which the element was taken (
p1orp2). - Increment
p.
- Compare
- After the main loop, one of the arrays might have remaining elements.
- If
p1 < m, copy the rest ofnums1_copyintonums1. - If
p2 < n, copy the rest ofnums2intonums1.
Walkthrough
This approach respects the sorted property of the arrays to achieve a linear time merge. However, merging from the beginning into nums1 would overwrite its elements before they are used for comparison. To solve this, we first create a backup of the initial m elements of nums1.
- Create a Copy: Make a copy of the first
melements ofnums1into a new array, saynums1_copy. - Initialize Pointers: Use three pointers:
p1to traversenums1_copy,p2to traversenums2, andpto write intonums1. - Merge: Compare elements at
nums1_copy[p1]andnums2[p2]. The smaller of the two is placed atnums1[p]. The corresponding pointers (p1orp2, andp) are then incremented. - Copy Remainder: Once one of the arrays is exhausted, the remaining elements from the other array are copied over to the end of
nums1.
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { // Make a copy of the first m elements of nums1. int[] nums1_copy = new int[m]; System.arraycopy(nums1, 0, nums1_copy, 0, m); // Pointers for nums1_copy, nums2, and the main nums1 array. int p1 = 0; int p2 = 0; int p = 0; // Compare elements from nums1_copy and nums2 and write the smaller one into nums1. while (p1 < m && p2 < n) { if (nums1_copy[p1] <= nums2[p2]) { nums1[p++] = nums1_copy[p1++]; } else { nums1[p++] = nums2[p2++]; } } // If there are remaining elements in nums1_copy, copy them. while (p1 < m) { nums1[p++] = nums1_copy[p1++]; } // If there are remaining elements in nums2, copy them. while (p2 < n) { nums1[p++] = nums2[p2++]; } }}Complexity
Time
O(m+n)
Space
O(m)
Trade-offs
Pros
Achieves linear time complexity, O(m+n).
Conceptually straightforward, similar to the merge step of the standard merge sort algorithm.
Cons
Requires extra space proportional to the number of initial elements in
nums1, which violates the O(1) space constraint for a truly in-place solution.
The optimal solution achieves linear time complexity with constant extra space. The key insight is to fill the nums1 array from the end towards the beginning. Since the last n elements of nums1 are empty (placeholders), we can place the largest elements of the merged array there without overwriting any data we still need to inspect. This avoids the need for an auxiliary array.
Algorithm
- Initialize three pointers:
p1pointing to the last valid element innums1(m - 1).p2pointing to the last element innums2(n - 1).ppointing to the very end ofnums1(m + n - 1).
- Loop backwards from the end of the arrays as long as there are elements to compare in both (
p1 >= 0andp2 >= 0). - In each iteration, compare
nums1[p1]andnums2[p2]. - Copy the larger of the two elements to
nums1[p]. - Decrement the pointer of the array from which the element was taken (
p1orp2). - Decrement the write pointer
p. - After the loop, copy any remaining elements from
nums2to the beginning ofnums1. (No need to handle remainingnums1elements as they are already in place).
Walkthrough
This approach cleverly utilizes the available space at the end of nums1 to perform the merge in-place without needing an auxiliary array. By filling the merged array from the end, we ensure that we never overwrite a value in nums1 that we haven't processed yet.
- Initialize Pointers: Set up three pointers.
p1points to the last valid element ofnums1(m-1),p2points to the last element ofnums2(n-1), andp(the write pointer) points to the last index ofnums1(m+n-1). - Merge from End: In a loop, compare the elements at
nums1[p1]andnums2[p2]. The larger element is placed atnums1[p]. The pointer corresponding to the larger element is decremented, and the write pointerpis also decremented. - Handle Remaining
nums2Elements: The loop continues until one of the pointers (p1orp2) goes below 0. Ifp2is still non-negative, it means there are elements left innums2that are smaller than all the processed elements. These remainingnums2elements are copied into the remaining empty slots at the beginning ofnums1. - No Action for
nums1: Ifp1is still non-negative, the elements it points to are already in their correct final positions, so no further action is needed.
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { // Pointer for the last element of the initial part of nums1 int p1 = m - 1; // Pointer for the last element of nums2 int p2 = n - 1; // Pointer for the last position in nums1 int p = m + n - 1; // Iterate from the end of both arrays while (p1 >= 0 && p2 >= 0) { // Place the larger element at the end of nums1 if (nums1[p1] > nums2[p2]) { nums1[p] = nums1[p1]; p1--; } else { nums1[p] = nums2[p2]; p2--; } p--; } // If there are remaining elements in nums2, copy them. while (p2 >= 0) { nums1[p] = nums2[p2]; p2--; p--; } }}Complexity
Time
O(m+n)
Space
O(1)
Trade-offs
Pros
Optimal time complexity of O(m+n).
Optimal space complexity of O(1) as it performs the merge in-place.
Elegant solution that cleverly uses the available space.
Cons
Can be slightly less intuitive to come up with compared to the auxiliary array approach.
Solutions
Solution
class Solution {public void merge(int[] nums1, int m, int[] nums2, int n) { for (int i = m - 1, j = n - 1, k = m + n - 1; j >= 0; --k) { nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--]; } }}/** * @param {number[]} nums1 * @param {number} m * @param {number[]} nums2 * @param {number} n * @return {void} Do not return anything, modify nums1 in-place instead. */ var merge = function (nums1, m, nums2, n) { for (let i = m - 1, j = n - 1, k = m + n - 1; j >= 0; --k) { nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--]; } };class Solution {public: void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) { for (int i = m - 1, j = n - 1, k = m + n - 1; ~j; --k) { nums1[k] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--]; } }};class Solution: def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None: """ Do not return anything, modify nums1 in-place instead. """ i, j, k = m - 1, n - 1, m + n - 1 # what if j=-1 already but k is not 0 yet? e.g. m=[1,2,0], n=[3] # => then no more ops needed, rest of m[] already sorted, so this while is good enough while j >= 0 : # i could be -1, eg. [7,8,9, ] and [1] if i >= 0 and nums1 [ i ] > nums2 [ j ]: nums1 [ k ] = nums1 [ i ] i -= 1 else : nums1 [ k ] = nums2 [ j ] j -= 1 k -= 1Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.