In today’s post, we’ll discuss the Merge Sorted Array problem from Leetcode.
Table of Contents
The Merge Sorted Array Problem
For this problem, we’re given two sorted integer arrays (known as lists in Python), nums1 and nums2, and our job is to merge nums2 into nums1 as one sorted list.
nums1 consists of m +n elements, m of which are initialized (i.e. non zero) and the rest are zeros.
nums2 consists of n elements, all of which are initialized.
For instance, suppose
nums1 = [1, 4, 5, 0, 0] nums2 = [2, 6]
3 of the elements in nums1 are initialized and 2 in nums2 are. Hence,
m = 3 n = 2
Our job is to write a function called merge() that takes four arguments – nums1, m, nums2 and n.
nums1 and nums2 are lists of integers while m and n are integers.
The function merges nums2 into nums1 as one sorted list and does not return any value (i.e. it modifies nums1 directly). After merging, nums1 becomes [1, 2, 4, 5, 6].
Suggested Approach
To work on the merge sorted array problem, we can take the following approach:
Start from the last initialized elements in both lists, compare the two elements and copy the larger element to the end of nums1.
Example
For instance, suppose
nums1 = [1, 3, 4, 0, 0] m = 3 nums2 = [2, 5] n = 2
We first compare 4 in nums1 with 5 in nums2 .
Since 5 is greater than 4, we copy 5 to the end of nums1.
nums1 becomes [1, 3, 4, 0, 5].
For ease of reference, in this tutorial, we’ll refer to 5 as an allocated element (i.e. an element that has been allocated/copied to the correct position).
Our job is to keep comparing the largest unallocated element in nums1 with the largest unallocated element in nums2 and copy the larger of the two to the correct position in nums1 .
For instance, to continue with our example, after allocating 5 to the end of nums1 , we move on to compare 4 in nums1 with 2 in nums2.
Since 4 is greater than 2, we copy 4 to nums1 and place it before the previous allocated number.
Hence, nums1 becomes [1, 3, 4, 4, 5].
We keep doing this comparison and allocation until all the elements in either nums1 or nums2 have been allocated.
Two Possible Cases
There can be two possible cases – either all the elements in nums1 are allocated first, or all the elements in nums2 are allocated first.
Let’s consider the two cases:
Case 1 – All the elements in nums1 are allocated first.
Suppose
nums1 = [3, 4, 6, 0, 0] nums2 = [1, 5]
After comparing the elements,
nums1 becomes [3, 3, 4, 5, 6].
All the elements in nums1 have been allocated to their correct positions (refer to the elements in red).
On the other hand, only one element in nums2 has been allocated (refer to the element in blue). The first element in nums2 has not been allocated as it is smaller than all the other elements. Hence, it ‘loses’ the competition each time we do a comparison.
As such, we need to copy this unallocated element to the front of nums1 , since nums1 is sorted in ascending order (i.e. the smallest element is at the front of the list).
nums1 thus becomes [1, 3, 4, 5, 6], which is the correct answer.
Case 2 – All the elements in nums2 allocated first.
If all the elements in nums2 are allocated first, we do not need to do anything else. This is because the unallocated elements in nums1 are already in the correct positions.
For instance, suppose
nums1 = [1, 3, 5, 0, 0] nums2 = [4, 6]
After comparing the elements,
nums1 becomes [1, 3, 4, 5, 6].
All the elements in nums2 have been allocated (refer to the elements in red).
On the other hand, only the last initialized element in nums1 has been allocated (refer to the element in blue). The remaining elements (i.e. 1 and 3) have not been allocated.
However, as nums1 is a sorted list, if there are any elements in nums1 that have not been allocated, they will be at the front of the list. Hence, there is no need to move these elements.
As such, nums1 = [1, 3, 4, 5, 6] is the result that we want.
Based on the description above, try solving this challenge yourself.
Graphical Illustration
Here’s a graphical illustration of how the approach above works for the Merge Sorted Array problem, using
nums1 = [3, 4, 6, 0, 0], m = 3, nums2 = [1, 5], n = 2
as an example:
Suggested Solution
Here’s the suggested solution for the Merge Sorted Array problem in Python:
def merge(nums1, m, nums2, n):
pointer = len(nums1) - 1
m = m - 1
n = n - 1
while m >= 0 and n >= 0:
if nums1[m] >= nums2[n]:
nums1[pointer] = nums1[m]
m -= 1
else:
nums1[pointer] = nums2[n]
n -= 1
pointer -= 1
if n >= 0:
nums1[:n+1] = nums2[:n+1]m, n and pointer
In the suggested solution above, we use m and n to keep track of the elements in nums1 and nums2 we are comparing, and pointer to keep track of the position to copy the larger element into.
At the start of the function (on lines 2 to 4), we first assign the correct values to pointer, m and n.
Suppose
nums1 = [1, 3, 4, 0, 0] nums2 = [2, 5] m = 3 n = 2
We let pointer be len(nums1) - 1 = 5 - 1 = 4 (i.e. index of the last element in nums1 ), m be 2 (index of the last initialized element in nums1 ) and n be 1 (index of the last initialized element in nums2 ).
Merging nums1 and nums2
Next, we use a while loop (from lines 6 to 16) to merge nums1 and nums2.
On line 8, we check if nums1[m] is greater than nums2[n]. If it is, we copy the element at nums1[m] to nums1[pointer] and decrement m by 1. Else, we copy the element at nums2[n] to nums1[pointer] and decrement n by 1.
After copying the larger element to nums1[pointer], we decrement the value of pointer by 1 and run the while loop again.
We keep running the while loop until either m or n has a value of -1 (i.e. until the while condition on line 6 is no longer valid).
When that happens, we have successfully copied all the elements in either nums1 or nums2 to the correct position.
Merging any remaining elements in nums2
Now, we need to check if there are any elements left in nums2 (i.e. if there are any elements in nums2 that have not been copied to nums1). We do that by checking the value of n on line 18.
If there are any unallocated elements left in nums2, n will be greater than or equal to zero. In that case, we assign the first n elements in nums2 to the first n elements in nums1.
On the other hand, if there are no unallocated elements in nums2, we do not need to do anything.
At this point, nums1 stores the correct answer that we need and the function is complete.
Graphical Examples
If you need help with the Merge Sorted Array Python solution above, you can refer to the illustration below for two examples on how the solution works:
