Merge Sorted Array

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.

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]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Can you come up with an algorithm that runs in O(m + n) time?

## Merging Sorted Arrays

This problem requires merging two sorted arrays, `nums1` and `nums2`, into a single sorted array, which should be stored in `nums1`. The `nums1` array has enough space to accommodate all elements from `nums2`.  The challenge lies in performing the merge in-place and efficiently.

### 1. Brute Force Solution

One straightforward approach is to copy the elements of `nums2` into the available space at the end of `nums1`, and then sort the entire `nums1` array. This method is simple to implement but not the most efficient.

```python
def merge_bruteforce(nums1, m, nums2, n):
    # Copy nums2 into nums1 starting from index m
    for i in range(n):
        nums1[m + i] = nums2[i]
    
    # Sort the entire nums1 array
    nums1.sort()

    return nums1

2. Optimal Solution: Two Pointers (Starting from the End)

A more efficient approach involves using two pointers, one for each array, and starting the merge from the end of the arrays. This way, we avoid overwriting elements in nums1 that haven't been processed yet. We compare the elements at the pointers and place the larger one at the end of nums1, moving the respective pointer accordingly. This continues until we exhaust one of the arrays. Finally, any remaining elements in the other array are copied into nums1.

def merge_optimal(nums1, m, nums2, n):
    # Initialize pointers at the end of the arrays
    p1 = m - 1
    p2 = n - 1
    p = m + n - 1

    # Merge elements starting from the end of nums1
    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

    # Copy any remaining elements from nums2 into nums1
    while p2 >= 0:
        nums1[p] = nums2[p2]
        p2 -= 1
        p -= 1

    return nums1

3. Big(O) Run-time Analysis

Brute Force:

• Copying elements: O(n)
• Sorting: O((m+n)log(m+n))
• Total: O((m+n)log(m+n))

Optimal (Two Pointers):

• The while loops iterate through the arrays at most once, giving us O(m + n).
• Therefore, the time complexity is O(m + n).

4. Big(O) Space Usage Analysis

Brute Force:

• The .sort() method sorts in-place, so the space complexity is O(1) or O(log(n)) depending on the implementation.

Optimal (Two Pointers):

• This solution operates in-place, modifying nums1 directly. No additional data structures are used that scale with the input size.
• Therefore, the space complexity is O(1).

5. Edge Cases

• nums2 is empty (n = 0):
  • The optimal solution handles this case correctly. The while loop condition p2 >= 0 ensures that if nums2 is empty, the loop won't execute, and nums1 remains unchanged.
• nums1 is empty (m = 0):
  • If nums1 is empty, the optimal solution correctly copies all elements from nums2 into nums1. The second while loop while p2 >= 0 handles this scenario.
• Overlapping values:
  • If there are overlapping values in nums1 and nums2, the optimal solution ensures that they are correctly merged in non-decreasing order due to the comparison nums1[p1] > nums2[p2].

Example:

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

Here's how the optimal solution merges the arrays:

1. p1 = 2, p2 = 2, p = 5
   • nums1[2] (3) > nums2[2] (6) is false. nums1[5] = 6, p = 4, p2 = 1
2. p1 = 2, p2 = 1, p = 4
   • nums1[2] (3) > nums2[1] (5) is false. nums1[4] = 5, p = 3, p2 = 0
3. p1 = 2, p2 = 0, p = 3
   • nums1[2] (3) > nums2[0] (2) is true. nums1[3] = 3, p = 2, p1 = 1
4. p1 = 1, p2 = 0, p = 2
   • nums1[1] (2) > nums2[0] (2) is false. nums1[2] = 2, p = 1, p2 = -1
5. p2 < 0, so copy remaining elements from nums1. nums1[1] = 2, nums1[0] = 1.

Final nums1: [1,2,2,3,5,6]