Watch 10 video solutions for Merge Sorted Array, a easy level problem involving Array, Two Pointers, Sorting. This walkthrough by NeetCode has 438,617 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 are given two sorted arrays nums1 and nums2. The first array has enough trailing space to hold all elements of the second. 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 most direct solution is to copy the first m valid elements of nums1 and all n elements of nums2 into a temporary array. After combining them, run a sorting algorithm to restore sorted order. This works because sorting guarantees the correct ordering regardless of how the elements were merged. The implementation is simple and easy to reason about, but it wastes memory and performs unnecessary sorting even though both arrays are already sorted.
Approach 2: Start from the End with Two Pointers (Time: O(m+n), Space: O(1))
The optimal solution leverages the fact that both arrays are already sorted. Instead of merging from the front, place three pointers: one at the end of the valid portion of nums1 (m-1), one at the end of nums2 (n-1), and one at the very end of nums1 (m+n-1). Compare elements from the back and write the larger value into the last available position in nums1. Move the corresponding pointer backward and repeat. This avoids overwriting useful values because you always fill unused positions from the end.
This technique is a classic Two Pointers pattern applied to a sorted Array. Each element is processed exactly once, resulting in linear time O(m+n) and constant auxiliary space O(1). No additional data structures are required.
Recommended for interviews: Interviewers expect the two-pointer approach that starts from the end. It demonstrates that you recognize the sorted property and can avoid unnecessary sorting. Showing the extra-space method first proves baseline problem understanding, but implementing the backward merge with O(m+n) time and O(1) space shows stronger algorithmic reasoning. The pattern also appears in other problems involving merging sorted sequences and sorting-related optimizations.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Use Extra Space to Combine and Sort | O((m+n) log(m+n)) | O(m+n) | Simple implementation when memory usage is not a concern |
| Two Pointers from the End (In‑Place Merge) | O(m+n) | O(1) | Best approach when arrays are already sorted and in-place merging is required |