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?
Problem Overview: You receive two sorted integer arrays nums1 and nums2 with sizes m and n. The first array has enough trailing space to hold all elements from both arrays. Your task is to merge nums2 into nums1 so that the final array remains sorted.
Approach 1: Use Extra Space to Combine and Sort (Time: O((m+n) log(m+n)), Space: O(m+n))
The straightforward method copies the first m elements of nums1 and all n elements of nums2 into a temporary array. After combining the values, apply a standard sort operation. This approach relies on built-in sorting algorithms such as quicksort or mergesort. The implementation is simple and easy to reason about, but it ignores the fact that both input arrays are already sorted. Because sorting dominates the runtime, the total complexity becomes O((m+n) log(m+n)) with O(m+n) additional memory. It works as a quick baseline but is rarely the optimal choice in interviews.
Approach 2: Start from the End with Two Pointers (Time: O(m+n), Space: O(1))
The optimal strategy uses the fact that both arrays are already sorted. Instead of merging from the front, place three pointers at the end: one at m-1 in nums1, one at n-1 in nums2, and one at m+n-1 where the next largest element should be written. Compare the values from both arrays and write the larger one into the back of nums1. Move the corresponding pointer and repeat until all elements from nums2 are placed.
This works because the extra space at the end of nums1 allows safe overwriting without losing unprocessed values. Each element is visited once, giving O(m+n) time and O(1) additional space. The technique is a classic two pointers pattern applied to sorted data. Problems involving merging sorted structures frequently rely on similar logic.
Understanding how sorted properties reduce work is key here. Instead of re-sorting the entire dataset, you only perform comparisons and pointer moves. The idea also appears in merge steps of merge sort and other sorting algorithms. Because the arrays are sequential structures, the implementation naturally fits common array manipulation patterns.
Recommended for interviews: The two-pointer approach from the end is the expected solution. Interviewers want to see that you recognize the unused buffer in nums1 and avoid unnecessary sorting. Mentioning the extra-space baseline first shows understanding of simpler strategies, but implementing the O(m+n) in-place merge demonstrates stronger algorithmic thinking.
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`.
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`.
Time Complexity: O(m + n); Space Complexity: O(1) since we do not use extra space.
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.
In C, we first append the elements of `nums2` onto `nums1`, and then employ the Quick Sort function `qsort` to sort the entire array.
Time Complexity: O((m + n) log (m + n)); Space Complexity: O(1) additional space aside from function call stack during sorting.
| Approach | Complexity |
|---|---|
| Start from the End with Two Pointers | Time Complexity: O(m + n); Space Complexity: O(1) since we do not use extra space. |
| Use Extra Space to Combine and Sort | Time Complexity: O((m + n) log (m + n)); Space Complexity: O(1) additional space aside from function call stack during sorting. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Combine then Sort | O((m+n) log(m+n)) | O(m+n) | Quick baseline solution when simplicity matters more than efficiency |
| Two Pointers from the End (In-place Merge) | O(m+n) | O(1) | Best choice when arrays are already sorted and memory must remain constant |
Merge Sorted Array - Leetcode 88 - Python • NeetCode • 340,421 views views
Watch 9 more video solutions →Practice Merge Sorted Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor