Difficulty: Easy | Acceptance: 54.80% | Paid: No Topics: Array, Two Pointers, Sorting
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.
- Examples
- Constraints
- Approach 1: Merge and Sort
- Approach 2: Two Pointers (Backwards)
- Approach 3: Two Pointers (Forward with Extra Space)
Examples
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
-10⁹ <= nums1[i], nums2[j] <= 10⁹
Approach 1: Merge and Sort
Intuition The simplest approach is to copy all elements from nums2 into the empty space at the end of nums1, and then sort the entire nums1 array.
Steps
- Copy the first n elements of nums2 into nums1 starting from index m.
- Use the built-in sort function of the language to sort nums1.
from typing import List
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.
"""
# Write the elements of nums2 into the end of nums1
for i in range(n):
nums1[m + i] = nums2[i]
# Sort the entire array
nums1.sort()
Complexity
- Time: O((m+n) log(m+n)) due to the sorting step.
- Space: O(1) or O(log(m+n)) depending on the sorting algorithm’s implementation (e.g., Timsort in Python uses O(n) space in worst case, Quicksort in C++ uses O(log n)).
- Notes: This approach is concise but not optimal in terms of time complexity since the arrays are already sorted.
Approach 2: Two Pointers (Backwards)
Intuition Since nums1 has enough buffer space at the end, we can fill nums1 from the back towards the front. This avoids overwriting any elements in nums1 that we haven’t processed yet. We compare the largest elements of both arrays and place the larger one at the current end of nums1.
Steps
- Initialize three pointers: p1 at m-1 (last valid element in nums1), p2 at n-1 (last element in nums2), and p at m+n-1 (last position in nums1).
- While p1 >= 0 and p2 >= 0, compare nums1[p1] and nums2[p2]. Place the larger value at nums1[p] and decrement the respective pointer (p1 or p2) and p.
- If there are remaining elements in nums2 (p2 >= 0), copy them to nums1. If there are remaining elements in nums1, they are already in their correct place.
from typing import List
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.
"""
# Set pointers for nums1, nums2, and the insertion position
p1 = m - 1
p2 = n - 1
p = m + n - 1
# Compare elements from the end and place the largest at the end of nums1
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
else:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
# If there are remaining elements in nums2, copy them
# If there are remaining elements in nums1, they are already in place
while p2 >= 0:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
Complexity
- Time: O(m+n) — We iterate through the arrays once.
- Space: O(1) — We only use a few variables for pointers.
- Notes: This is the optimal solution for this problem as it utilizes the existing space efficiently without overwriting unprocessed data.
Approach 3: Two Pointers (Forward with Extra Space)
Intuition We can create a new temporary array to store the merged result. We use two pointers starting at the beginning of nums1 and nums2, compare elements, and place the smaller one into the temporary array. Finally, we copy the temporary array back to nums1.
Steps
- Create a temporary array of size m + n.
- Initialize pointers i = 0 for nums1, j = 0 for nums2, and k = 0 for the temporary array.
- While i < m and j < n, compare nums1[i] and nums2[j]. Add the smaller one to temp[k] and increment the corresponding pointer.
- Copy any remaining elements from nums1 or nums2 to temp.
- Copy all elements from temp back to nums1.
from typing import List
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.
"""
# Create a temporary array to store the result
temp = []
i, j = 0, 0
# Merge elements in sorted order
while i < m and j < n:
if nums1[i] <= nums2[j]:
temp.append(nums1[i])
i += 1
else:
temp.append(nums2[j])
j += 1
# Append remaining elements from nums1
while i < m:
temp.append(nums1[i])
i += 1
# Append remaining elements from nums2
while j < n:
temp.append(nums2[j])
j += 1
# Copy temp back to nums1
for k in range(len(temp)):
nums1[k] = temp[k]
Complexity
- Time: O(m+n) — We traverse both arrays once.
- Space: O(m+n) — We use an extra array to store the merged result.
- Notes: This approach is intuitive and easy to understand but uses extra space, which is not optimal compared to the backwards two-pointer approach.