Merge Sorted Array Leetcode Problem 88 [Python Solution]

In this blog post, we will explore the LeetCode problem #88, Merge Sorted Array This problem falls under the category of "Two Pointers" and is considered to be an "Easy" difficulty level.

We will provide a Python solution that efficiently merges two sorted arrays and explain the reasoning behind our approach.

By the end of this guide, you will have a solid understanding of how to solve this problem.

Problem Overview

You are given two integer arrays, nums1 and nums2, both sorted in non-decreasing order.

Additionally, you are given two integers, m and n, which represent the number of elements in nums1 and nums2, respectively.

The task is to merge nums2 into nums1 to create a single sorted array in non-decreasing order.

It's important to note that the final sorted array should be stored inside the nums1 array itself. nums1 has a length of m + n, where the first m elements represent the elements that should be merged, and the last n elements are set to 0 and should be ignored.

On the other hand, nums2 has a length of n.

Let's consider an example to better understand the problem.

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]


In this example, we are merging two arrays: [1,2,3] (from nums1) and [2,5,6] (from nums2).

The result of the merge is [1,2,2,3,5,6], with the underlined elements coming from nums1.

Now, let's dive into the problem and its efficient solution.

Understanding the Constraints

Before we proceed, let's briefly discuss the constraints that the problem provides:

• nums1.length == m + n: This condition ensures that nums1 has enough space to accommodate the merged elements from nums2.
• nums2.length == n: This constraint defines the length of nums2.
• 0 <= m, n <= 200: The values of m and n are bounded between 0 and 200, indicating that these arrays can be relatively small.
• 1 <= m + n <= 200: The sum of m and n must be at least 1 and at most 200.
• -10^9 <= nums1[i], nums2[j] <= 10^9: The elements within nums1 and nums2 can be integers within a wide range.

Now that we understand the problem and its constraints, let's move on to the efficient Python code solution.

Efficient Python Code Solution

We will provide a Python solution to efficiently merge two sorted arrays, nums1 and nums2.

This solution follows the constraints and requirements of the problem.

def merge(nums1, m, nums2, n):
    """
    Do not return anything, modify nums1 in-place instead.
    """
    # Initialize pointers for the last positions in nums1, nums2, and the merged array.

last = m + n - 1
    m -= 1
    n -= 1

    # Merge elements from the end to the beginning.

while m >= 0 and n >= 0:
        if nums1[m] >= nums2[n]:
            nums1[last] = nums1[m]
            m -= 1
        else:
            nums1[last] = nums2[n]
            n -= 1
        last -= 1

    # Fill nums1 with any remaining elements from nums2 (if any).

while n >= 0:
        nums1[last] = nums2[n]
        n -= 1
        last -= 1

This Python function, merge, takes four parameters: nums1, m, nums2, and n.

It efficiently merges the two arrays and stores the result in nums1 in-place.

Let's break down the solution step by step:

1. We initialize a pointer, last, to keep track of the last position in nums1, where the merged elements will be stored.

2. We decrement m and n by 1 to represent the last index in each array.

3. We start the merging process from the end of the arrays and work our way to the beginning.

This ensures that we don't overwrite any elements in nums1 before they are merged.

1. Inside the while loop, we compare the last elements of both arrays (nums1[m] and nums2[n]).

If the element in nums1 is greater or equal, we place it in the last position of nums1 and decrement m.

If the element in nums2 is greater, we place it in the last position of nums1 and decrement n.

In both cases, we decrement last to move to the next position.

1. We continue this process until one of the arrays, nums1 or nums2, is completely merged into nums1.

2. After merging the elements from nums2 into nums1, we check if there are any remaining elements in nums2.

If there are, we fill the remaining positions in nums1 with these elements, ensuring that the merged array remains sorted.

By following this efficient approach, we merge the two sorted arrays in-place, using only a constant amount of extra memory.

This results in a time complexity of O(m + n), where m and n are the lengths of nums1 and nums2, respectively.

The space complexity is O(1) since we do not use additional data structures.

Reasoning Behind Our Approach

The key to this efficient solution is taking advantage of the fact that nums1 has empty space at the end, allowing us to merge the elements in reverse order without the need for additional memory.

By starting from the end of both arrays and working our way to the beginning, we ensure that the merged array is created in the correct order.

The while loop compares the last elements of both arrays, selects the larger element, and places it in the appropriate position in nums1.

The pointers are updated accordingly, and the loop continues until one of the arrays is fully merged.

This approach optimally utilizes the available space in nums1 and minimizes the number of operations needed.

Related Interview Questions By Company:

• Baseball Game LeetCode
• Kth Largest Element In A Stream LeetCode
• Longest Common Prefix LeetCode

Related Interview Questions By Difficulty:

• Remove Duplicates From Sorted Array LeetCode
• Reverse String LeetCode
• Merge Sorted Array LeetCode

Related Interview Questions By Category:

• Interleaving String LeetCode
• Course Schedule LeetCode
• Longest Repeating Character Replacement LeetCode

Conclusion

In this blog post, we've explored the LeetCode problem #88, "Merge Sorted Array," and provided an efficient Python solution.

We've also discussed the constraints of the problem, which help guide our approach.

By merging the two sorted arrays in reverse order, we avoid the need for extra memory and efficiently create the final merged array in-place.

We hope this guide has been helpful in understanding how to tackle this problem.

If you have any questions, suggestions, or comments, please feel free to share them.

We encourage you to explore more

coding challenges and keep honing your skills.

You can find the original question on LeetCode here.

Thank you for reading, and happy coding!