Merge Sorted Array
Problem Description
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 + n
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= 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?
Solve it on LeetCode
Approaches
1. Merge Then Sort
Intuition:
The simplest approach to solve the problem is to first merge the elements of nums2 into nums1 and then sort nums1. Although it is not the most efficient solution, it works for small inputs and provides an easy starting point.
Steps:
- Copy all elements from
nums2intonums1starting from indexm. - Sort the array
nums1.
Code:
- Time Complexity: O((m+n)log(m+n)), due to sorting.
- Space Complexity: O(1), as we are modifying nums1 in place.
2. Two-Pointer
Intuition:
Both arrays nums1 and nums2 are sorted, thus we can use a two-pointer technique to merge them efficiently. Create a new array to store the merged sorted elements.
Steps:
- Initialize three pointers:
p1fornums1,p2fornums2, andpfor the new array. - Compare elements pointed by
p1andp2, and place the smaller one in the new array. - If any elements are left in
nums1ornums2, append them to the end of the new array. - Copy the new array back into
nums1.
Code:
- Time Complexity: O(m + n), as we iterate through both arrays once.
- Space Complexity: O(m + n), due to the use of an additional array.
3. In-place Two-Pointer
Intuition:
Since the space in nums1 after m is unused, leverage this space to place the merged results directly. We'll move backwards from the end of the arrays to avoid overwriting any values.
Steps:
- Use two pointers
p1andp2starting from the end of the initialized parts ofnums1andnums2respectively, and another pointerpfrom the very end ofnums1. - Compare the current elements of
nums1andnums2and place the larger one at thepposition. - Decrement the respective pointers.
- If any elements are left in
nums2, copy them tonums1(no need to handle the remainingnums1, they are already in place).
Code:
- Time Complexity: O(m + n), as we process each element exactly once.
- Space Complexity: O(1), since we are merging in-place without extra space.