88. Merge Sorted Array
Problem Description
You have two sorted arrays nums1
and nums2
with lengths m
and n
, respectively. These arrays are sorted in non-decreasing order, which means each element is equal to or greater than the previous element. Initially, the array nums1
has m
elements in it, and an additional n
spaces filled with 0
to allow space for merging. The array nums2
has exactly n
elements.
The goal is to merge these two arrays so that the nums1
array becomes a single sorted array in non-decreasing order. The merge should happen in-place in the nums1
array, using the additional space provided so that it can fit all m + n
elements by the end.
Intuition
The challenge is to merge the two sorted arrays in-place, without using extra space for another array. Our intuition might suggest starting from the beginning of both arrays and comparing the elements one by one. However, this approach would require shifting elements in nums1
to make space for elements from nums2
, which is not efficient.
To efficiently merge these arrays, we leverage the fact that we have empty space at the end of nums1
where n
zeros are placed. This allows us to fill nums1
from the end (right to left), placing the largest elements first and avoiding the need for shifting.
We use a two-pointer approach. The first pointer i
starts at the last actual element in nums1
, and the second pointer j
starts at the last element in nums2
. We also have a third pointer k
that starts at the very end of nums1
, and it indicates where the next element should be placed.
Each step involves comparing the elements pointed by i
and j
. The larger of the two elements is placed at the position indicated by k
, and then we move the respective pointer (i
or j
) and k
one step back. We repeat this process until all elements from nums2
are placed into nums1
. If nums1
still has elements left when nums2
runs out, they are already in place as the array is sorted. If nums2
had the greatest element, it would be placed last, ensuring the non-decreasing order is maintained throughout the process.
Learn more about Two Pointers and Sorting patterns.
Solution Approach
The implementation of the solution starts with the recognition that by merging the arrays from right to left, you can avoid additional space complexities and time-consuming operations like shifting elements.
The pointers i
, j
, and k
are initialized as follows: i
starts at m - 1
, j
at n - 1
, and k
at m + n - 1
.
The algorithm is inherently a comparison between the elements pointed to by i
and j
. Let's walk through the steps:
- Compare the elements at pointer
i
innums1
and at pointerj
innums2
. - If
nums1[i]
is greater, placenums1[i]
innums1[k]
, and decrement bothi
andk
. - If
nums2[j]
is greater ori
is out of bounds (which means all elements ofnums1
have been placed), placenums2[j]
innums1[k]
, and decrement bothj
andk
.
This logic is concisely written in a loop that continues until all elements of nums2
are processed, which is when j < 0
. The condition i >= 0 and nums1[i] > nums2[j]
ensures that you are still within bounds of nums1
and that the current element in nums1
is indeed larger than nums2[j]
.
while j >= 0: if i >= 0 and nums1[i] > nums2[j]: nums1[k] = nums1[i] i -= 1 else: nums1[k] = nums2[j] j -= 1 k -= 1
This approach does not require any extra data structures. It utilizes the space already allocated within nums1
and takes advantage of the sorted order, allowing an efficient in-place merge. The pattern used here is commonly known as the two-pointer technique, which is often applied to problems that involve sorted arrays.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach.
Assume our nums1
array is [1, 2, 3, 0, 0, 0]
with m = 3
, and our nums2
array is [2, 5, 6]
with n = 3
. The goal is to merge nums2
into nums1
so that it becomes a single sorted array.
Following the steps described in the solution approach:
- Set
i
tom - 1
, which is2
, pointing at the last actual element innums1
. - Set
j
ton - 1
, which is2
, pointing at the last element innums2
. - Set
k
tom + n - 1
, which is5
, pointing to the last space innums1
.
Now we begin comparing and placing elements:
-
First iteration:
- Compare
nums1[i]
(which is3
) andnums2[j]
(which is6
). - Since
nums2[j]
is greater, we place6
innums1[k]
. - Decrement
j
to1
andk
to4
. - Now,
nums1
looks like[1, 2, 3, 0, 0, 6]
.
- Compare
-
Second iteration:
- Compare
nums1[i]
(which is3
) andnums2[j]
(which is5
). - Since
nums2[j]
is greater, we place5
innums1[k]
. - Decrement
j
to0
andk
to3
. - Now,
nums1
looks like[1, 2, 3, 0, 5, 6]
.
- Compare
-
Third iteration:
- Compare
nums1[i]
withnums2[j]
(which is2
). nums1[i]
is3
which is greater thannums2[j]
.- Place
nums1[i]
innums1[k]
, then decrementi
to1
andk
to2
. - Now,
nums1
looks like[1, 2, 3, 3, 5, 6]
.
- Compare
-
Fourth iteration:
- Compare
nums1[i]
(which is2
) andnums2[j]
(which is2
). - They are equal, but it doesn't matter which one we choose. Here's we choose
nums2[j]
. - Place
nums2[j]
innums1[k]
, then decrementj
to-1
andk
to1
. - Now,
nums1
looks like[1, 2, 2, 3, 5, 6]
.
- Compare
Since j
is now -1
, we have placed all elements from nums2
into nums1
. The elements from nums1
that have not yet been moved are already correctly placed because nums1
was sorted to begin with. Our merged array is [1, 2, 2, 3, 5, 6]
, which is sorted in non-decreasing order.
Solution Implementation
1from typing import List
2
3class Solution:
4 def merge(self, nums1: List[int], total_nums1: int, nums2: List[int], total_nums2: int) -> None:
5 """
6 Merges two sorted arrays, nums1 and nums2, into a single sorted array.
7 The first array nums1 has a size sufficient to hold the contents of both arrays.
8 The merge is done in-place.
9
10 :param nums1: List[int], the first sorted array with extra space for nums2.
11 :param total_nums1: int, the number of valid elements in nums1.
12 :param nums2: List[int], the second sorted array to be merged into nums1.
13 :param total_nums2: int, the number of elements in nums2.
14 """
15 # Initialize pointers for nums1 and nums2 starting from the end of their valid elements
16 index_nums1, index_nums2 = total_nums1 - 1, total_nums2 - 1
17
18 # Start filling nums1 from the end, to avoid overwriting elements of nums1 that are not yet merged
19 merge_index = total_nums1 + total_nums2 - 1
20
21 # Merge in reverse order
22 while index_nums2 >= 0:
23 # If nums1 is not yet exhausted and the current element is larger than nums2's, place it in the current position
24 if index_nums1 >= 0 and nums1[index_nums1] > nums2[index_nums2]:
25 nums1[merge_index] = nums1[index_nums1]
26 index_nums1 -= 1 # Move the nums1 index backwards
27 else:
28 # Else, place element from nums2
29 nums1[merge_index] = nums2[index_nums2]
30 index_nums2 -= 1 # Move the nums2 index backwards
31 merge_index -= 1 # Move the merge index backwards
32
1class Solution {
2 // Merges two sorted arrays, nums1 and nums2, into a single sorted array.
3 public void merge(int[] nums1, int m, int[] nums2, int n) {
4 // Initialize pointers for nums1, nums2 and the merged array.
5 int indexNums1 = m - 1; // Pointer for the last element in the nums1's original part
6 int indexNums2 = n - 1; // Pointer for the last element in nums2
7 int mergedIndex = m + n - 1; // Pointer for the last element of merged array (end of nums1)
8
9 // Iterate over nums2 and nums1 from the end of both arrays
10 while (indexNums2 >= 0) {
11 // If nums1 is exhausted, or the current element in nums2 is larger
12 if (indexNums1 < 0 || nums1[indexNums1] <= nums2[indexNums2]) {
13 nums1[mergedIndex] = nums2[indexNums2]; // Place nums2's element in the merged array
14 indexNums2--; // Move to the next element in nums2
15 } else {
16 // The current element in nums1 is larger; place it in the merged array
17 nums1[mergedIndex] = nums1[indexNums1];
18 indexNums1--; // Move to the next element in nums1
19 }
20 mergedIndex--; // Move to the next position in the merged array
21 }
22 // No need to check the remaining elements of nums1,
23 // if any left, since they are already in their sorted position.
24 }
25}
26
1class Solution {
2public:
3 void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
4 // Initialize two pointers for the end of the two arrays and
5 // one pointer for the end of the merged array
6 int nums1Index = m - 1; // Pointer for the end of nums1
7 int nums2Index = n - 1; // Pointer for the end of nums2
8 int mergeIndex = m + n - 1; // Pointer for the end of the merged array (nums1)
9
10 // Iterate through nums1 and nums2 from the end until all elements from nums2 are inserted
11 while (nums2Index >= 0) {
12 // If there are still elements in nums1 and the current
13 // element of nums1 is larger than that of nums2
14 if (nums1Index >= 0 && nums1[nums1Index] > nums2[nums2Index]) {
15 // Place the element of nums1 in the correct position of the merged array
16 nums1[mergeIndex] = nums1[nums1Index];
17 nums1Index--; // Move the pointer of nums1 to the left
18 } else {
19 // Place the element of nums2 in the correct position of the merged array
20 nums1[mergeIndex] = nums2[nums2Index];
21 nums2Index--; // Move the pointer of nums2 to the left
22 }
23 mergeIndex--; // Move the pointer of the merged array to the left
24 }
25 // No need to copy the remaining elements of nums1, if any, since they are already in place.
26 }
27};
28
1// Merges two sorted arrays nums1 and nums2 into nums1 in sorted order.
2// The first m elements of nums1 contain the initial sorted elements
3// and nums1 has enough space to hold the additional elements from nums2.
4// The arguments n and m represent the number of elements in nums2 and nums1, respectively.
5function merge(nums1: number[], countNums1: number, nums2: number[], countNums2: number): void {
6 // Initialize pointers:
7 // lastNums1Index - Pointer for the last element in nums1's initial sorted part.
8 // lastNums2Index - Pointer for the last element in nums2.
9 // mergedIndex - Pointer for the last position in nums1 where we will place the merged element.
10 let lastNums1Index: number = countNums1 - 1;
11 let lastNums2Index: number = countNums2 - 1;
12 let mergedIndex: number = countNums1 + countNums2 - 1;
13
14 // Merge in reverse order to avoid overwriting elements in nums1 that have not been checked yet.
15 while (lastNums2Index >= 0) {
16 // Check and compare elements from nums1 and nums2.
17 // Place the larger element in the correct sorted position at the end of nums1.
18 nums1[mergedIndex--] = lastNums1Index >= 0 && nums1[lastNums1Index] > nums2[lastNums2Index]
19 ? nums1[lastNums1Index--] // Use the element from nums1 and decrement the pointer.
20 : nums2[lastNums2Index--]; // Use the element from nums2 and decrement the pointer.
21 }
22}
23
Time and Space Complexity
The given code has a time complexity of O(m + n)
since it involves iterating over the elements of nums1
and nums2
in reverse order, where m
and n
are the lengths of the respective arrays. It's a single pass through the combined size of both arrays, hence the addition of m
and n
.
The space complexity of the code is O(1)
, as it only uses a constant amount of extra space. The merging is done in place and does not require any additional data structures that scale with the input size.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the relationship between a tree and a graph?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!