Leetcode – Merge Sorted Array in Python

Spread the love

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.

Problem Statement

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 = [1], m = 1, nums2 = [], n = 0 Output: [1]

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 nums1 and nums2, and their lengths m and n.

def merge(nums1, m, nums2, n):

Step 2: Initialize Pointers

We’ll initialize three pointers: p1 to the end of the meaningful part of nums1, p2 to the end of nums2, and p to the end of nums1.

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 p1 and p2, place the larger one at position p in nums1, and move the pointers accordingly. This continues until p1 or 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 nums1.

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], 1, [], 0)
print(nums1) # Output: [1]

Our solution correctly merges the arrays in place and produces the correct output.

Conclusion

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.

Leave a Reply