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:

- Initialize two pointers,
`p1`

and`p2`

, pointing to the last valid elements of`nums1`

and`nums2`

, respectively. - Initialize a third pointer,
`p`

, pointing to the last element of the merged array. - Compare the elements at
`nums1[p1]`

and`nums2[p2]`

. Place the larger element at`nums1[p]`

. - Decrement
`p`

and`p1`

(if the element was from`nums1`

) or`p2`

(if the element was from`nums2`

). - 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

- 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. - 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. - 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. - If the element in
`nums2`

is larger or equal, we place it at`nums1[p]`

and decrement`p2`

by 1. - In either case, we decrement
`p`

by 1 to move to the previous position in the merged array. - 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.