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] <= 109Follow up: Can you come up with an algorithm that runs in O(m + n) time?
The key idea in Merge Sorted Array is to merge two already sorted arrays into one sorted array while respecting the extra space provided in the first array. A naive method would copy elements into a new array and then sort it, but that increases time and space usage.
A more optimal strategy uses the two-pointer technique. Start comparing elements from the end of both arrays and place the larger value at the back of the first array. This works because the first array has enough trailing space to hold all elements. By filling the array from the end, we avoid overwriting useful values that still need comparison.
This approach processes each element only once, giving a time complexity of O(m + n). Since the merge happens directly inside the first array without allocating extra storage, the space complexity remains O(1). Understanding pointer movement and boundary conditions is the main challenge in implementing this technique.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting after concatenation | O((m+n) log(m+n)) | O(1) or O(n) depending on sort |
| Two Pointers from the End (Optimal) | O(m + n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
You can easily solve this problem if you simply think about two elements at a time rather than two arrays. We know that each of the individual arrays is sorted. What we don't know is how they will intertwine. Can we take a local decision and arrive at an optimal solution?
If you simply consider one element each at a time from the two arrays and make a decision and proceed accordingly, you will arrive at the optimal solution.
The most efficient way to merge two sorted arrays without using extra space is by using a two-pointer approach from the end. You start comparing elements from the end of both arrays and fill `nums1` from the back. This way you avoid needing additional space for a temporary array and can overwrite existing data in `nums1`.
Time Complexity: O(m + n); Space Complexity: O(1) since we do not use extra space.
1#include <stdio.h>
2
3void merge(int* nums1, int m, int* nums2, int n) {
4 int i = m - 1;
5 int j = n - 1;
6 int k = m + n - 1;
7
8 while (i >= 0 && j >= 0) {
9 if (nums1[i] > nums2[j]) {
10 nums1[k--] = nums1[i--];
11 } else {
12 nums1[k--] = nums2[j--];
13 }
14 }
15
16 while (j >= 0) {
17 nums1[k--] = nums2[j--];
18 }
19}
20
21int main() {
22 int nums1[] = {1, 2, 3, 0, 0, 0};
23 int nums2[] = {2, 5, 6};
24 merge(nums1, 3, nums2, 3);
25 for (int i = 0; i < 6; i++) {
26 printf("%d ", nums1[i]);
27 }
28 return 0;
29}This C implementation uses a two-pointer technique starting from the back of the arrays `nums1` and `nums2`. It compares elements of both arrays from the end and places the larger element at the current end position in `nums1`.
This is a less efficient approach that involves first combining the contents of `nums1` and `nums2` into a new array. Then, the new array is sorted, and its contents are copied back into `nums1`. Although straightforward, this approach involves extra memory allocation.
Time Complexity: O((m + n) log (m + n)); Space Complexity: O(1) additional space aside from function call stack during sorting.
1#
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Merge Sorted Array is a common interview question because it tests array manipulation and the two-pointer technique. Variations of this problem frequently appear in coding interviews at major tech companies.
Merging from the end prevents overwriting elements in the first array that still need to be compared. Since the array already has extra space at the back, placing the largest elements there ensures safe and efficient in-place merging.
The optimal approach uses the two-pointer technique starting from the end of both arrays. By placing the larger element at the back of the first array, you can merge them in-place without overwriting needed values. This results in O(m+n) time and O(1) extra space.
Arrays with pointer manipulation are sufficient for this problem. The solution mainly relies on index pointers rather than additional data structures. This allows the merge to happen directly within the existing array space.
In C, we first append the elements of `nums2` onto `nums1`, and then employ the Quick Sort function `qsort` to sort the entire array.