Among Leetcode’s wide array of problems, the ‘Merge Sorted Array’ is a very engaging and popular one. This problem helps enhance your understanding of array manipulation in Python. In this comprehensive article, we will discuss the problem, understand it, and solve it using Python.
The ‘Merge Sorted Array’ problem (LeetCode problem #88) states:
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, and contains the elements that should be merged into nums1.
Here are a few examples for better understanding:
- Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]
- Input: nums1 = , m = 1, nums2 = , n = 0 Output: 
Understanding the Problem
The problem requires us to merge two sorted arrays, nums1 and nums2, but the twist is that we need to do the merge operation in place, i.e., without using any extra space. The array nums1 has a size equal to the sum of the sizes of nums1 and nums2 and is initialized with the elements of nums1 followed by zeros. We are required to ignore these zeros during the merge operation. The goal is to fill up nums1 with the sorted, merged elements of nums1 and nums2.
Approach to Solve the Problem
One effective method to solve this problem is by using a two-pointer technique, working our way from the back of the arrays.
Step 1: Create a Function
We’ll start by creating a function called
merge that accepts four arguments: the two arrays
nums2, and their lengths
def merge(nums1, m, nums2, n):
Step 2: Initialize Pointers
We’ll initialize three pointers:
p1 to the end of the meaningful part of
p2 to the end of
p to the end of
def merge(nums1, m, nums2, n): p1 = m - 1 p2 = n - 1 p = m + n - 1
Step 3: Compare and Merge
We compare the elements at
p2, place the larger one at position
nums1, and move the pointers accordingly. This continues until
p2 goes out of bounds.
def merge(nums1, m, nums2, n): p1 = m - 1 p2 = n - 1 p = m + n - 1 while p1 >= 0 and p2 >= 0: if nums1[p1] < nums2[p2]: nums1[p] = nums2[p2] p2 -= 1 else: nums1[p] = nums1[p1] p1 -= 1 p -= 1
Step 4: Handle Remaining Elements
If there are still elements left in
nums2, they must be smaller than those in
nums1 and are placed at the beginning of
def merge(nums1, m, nums2, n): p1 = m - 1 p2 = n - 1 p = m + n - 1 while p1 >= 0 and p2 >= 0: if nums1[p1] < nums2[p2]: nums1[p] = nums2[p2] p2 -= 1 else: nums1[p] = nums1[p1] p1 -= 1 p -= 1 while p2 >= 0: nums1[p] = nums2[p2] p -= 1 p2 -= 1
This is our final solution. There is no need for a return statement as the function modifies
nums1 in place.
Testing the Solution
Let’s test our function with the sample inputs:
merge([1,2,3,0,0,0], 3, [2,5,6], 3) print(nums1) # Output: [1,2,2,3,5,6] merge(, 1, , 0) print(nums1) # Output: 
Our solution correctly merges the arrays in place and produces the correct output.
The ‘Merge Sorted Array’ problem is an excellent exercise for understanding array manipulation and the two-pointer technique in Python. By comparing elements from the back of the arrays, we can effectively perform the merge operation in place, thus meeting the problem’s requirements.