Tutorial: Merge Sorted Array – Python Solution

In this tutorial, we’ll explore the “Merge Sorted Array” question and provide a detailed Python solution. This question is a common interview problem that tests your ability to merge two sorted arrays into a single sorted array efficiently. We’ll discuss the problem statement, outline the approach, walk through the code implementation, and analyze its time and space complexity. By the end of this tutorial, you should have a clear understanding of how to solve the “Merge Sorted Array” question using Python.

Problem Statement

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. The merged array should be in non-decreasing order. You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The values of nums1 and nums2 are in non-decreasing order.

Here’s an example:

Input:
nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3

Output:
[1, 2, 2, 3, 5, 6]

Approach

The problem requires merging two sorted arrays, nums1 and nums2, into nums1. Since the arrays are already sorted, we can leverage this property to perform the merging efficiently.

A common approach is to start from the end of both arrays and work our way backwards. Since nums1 has enough space to hold all elements, we’ll fill in the largest elements first. This way, we won’t overwrite any elements in nums1 that haven’t been merged yet.

The steps of the approach can be summarized as follows:

1. Initialize two pointers, p1 and p2, pointing to the last valid elements of nums1 and nums2, respectively.
2. Initialize a third pointer, p, pointing to the last element of the merged array.
3. Compare the elements at nums1[p1] and nums2[p2]. Place the larger element at nums1[p].
4. Decrement p and p1 (if the element was from nums1) or p2 (if the element was from nums2).
5. Repeat steps 3-4 until all elements from nums2 have been merged into nums1.

Python Implementation

Let’s implement the approach step by step in Python:

def merge(nums1, m, nums2, n):
    p1, p2, p = m - 1, n - 1, m + n - 1

    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

    # If there are remaining elements in nums2
    nums1[:p2 + 1] = nums2[:p2 + 1]

Explanation

1. We initialize three pointers: p1 and p2 pointing to the last valid elements of nums1 and nums2, and p pointing to the last element of the merged array.
2. We enter a loop that continues as long as both p1 and p2 are greater than or equal to 0. This ensures that we have elements in both arrays to compare and merge.
3. We compare the elements at nums1[p1] and nums2[p2]. If the element in nums1 is larger, we place it at nums1[p] and decrement p1 by 1.
4. If the element in nums2 is larger or equal, we place it at nums1[p] and decrement p2 by 1.
5. In either case, we decrement p by 1 to move to the previous position in the merged array.
6. After the loop, if there are any remaining elements in nums2, we copy them to the beginning of nums1.

Time and Space Complexity Analysis

The time complexity of this solution is O(m + n), where m is the length of nums1 and n is the length of nums2. This is because we iterate through both arrays once using the pointers p1 and p2.

The space complexity of this solution is O(1) since we are modifying nums1 in place and not using any additional data structures that scale with the input sizes.

Testing the Solution

Let’s test the solution using the example provided in the problem statement:

nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3

merge(nums1, m, nums2, n)
print(nums1)  # Output: [1, 2, 2, 3, 5, 6]

Additional Test Cases

Here are some additional test cases to further validate the solution:

# Test Case 1
nums1 = [4, 5, 6, 0, 0, 0]
m = 3
nums2 = [1, 2, 3]
n = 3
merge(nums1, m, nums2, n)
print(nums1)  # Output: [1, 2, 3, 4, 5, 6]

# Test Case 2
nums1 = [1, 2, 3, 4, 0, 0, 0]
m = 4
nums2 = [5, 6, 7]
n = 3
merge(nums1, m, nums2, n)
print(nums1)  # Output: [1, 2, 3, 4, 5, 6, 7]

# Test Case 3
nums1 = [1, 3, 5, 0, 0]
m = 3
nums2 = [2, 4]
n = 2
merge(nums1, m, nums2, n)
print(nums1)  # Output: [1, 2, 3, 4, 5]

Conclusion

In this tutorial, we’ve successfully walked through the “Merge Sorted Array” question and provided a Python solution. We discussed the problem statement, outlined the approach, implemented the solution, and analyzed its time and space complexity. By following the steps outlined in this tutorial, you should now be well-equipped to solve the “Merge Sorted Array” question in Python efficiently. Remember that this approach takes advantage of the fact that both input arrays are sorted, allowing for an optimal merging process without requiring extra space.