# LeetCode 88: Merge Sorted Array

## Problem Restatement

We are given two integer arrays:

```python
nums1
nums2
```

Both arrays are sorted in non-decreasing order.

We are also given two integers:

```python
m
n
```

The first `m` elements of `nums1` are valid sorted elements.

The array `nums2` contains `n` valid sorted elements.

The total length of `nums1` is `m + n`, so it has enough space to hold all elements from both arrays.

We need to merge `nums2` into `nums1` in-place, so that `nums1` becomes one sorted array.

The function should not return the final array. It should modify `nums1` directly. The last `n` zeroes in `nums1` are placeholders and should be ignored before merging.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `nums1`, `m`, `nums2`, `n` |
| Output | Nothing returned |
| Mutation | Store the merged sorted result inside `nums1` |
| Valid part of `nums1` | First `m` elements |
| Valid part of `nums2` | All `n` elements |
| Placeholder part | Last `n` elements of `nums1` |

Function shape:

```python
class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        ...
```

## Examples

Example 1:

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

The valid arrays are:

```python
[1, 2, 3]
[2, 5, 6]
```

After merging:

```python
nums1 = [1, 2, 2, 3, 5, 6]
```

Example 2:

```python
nums1 = [1]
m = 1
nums2 = []
n = 0
```

There is nothing to merge from `nums2`.

After merging:

```python
nums1 = [1]
```

Example 3:

```python
nums1 = [0]
m = 0
nums2 = [1]
n = 1
```

There are no valid elements in `nums1`.

The `0` is only placeholder space.

After merging:

```python
nums1 = [1]
```

## First Thought: Use an Extra Array

A simple way is to copy the valid part of `nums1` and all of `nums2` into a new array, sort it, then copy it back.

```python
merged = nums1[:m] + nums2
merged.sort()
nums1[:] = merged
```

This works, but it does not use the sorted structure fully.

It also uses extra space.

We can do better by merging directly.

## Key Insight

Both arrays are already sorted.

If we merge from the front, we may overwrite valid elements in `nums1`.

Example:

```python
nums1 = [1, 2, 3, 0, 0, 0]
nums2 = [2, 5, 6]
```

If we place `2` from `nums2` near the front, we may overwrite `2` or `3` from the valid part of `nums1`.

But `nums1` has empty space at the back.

So we merge from the back.

The largest remaining value among both arrays belongs at the last open position in `nums1`.

Use three pointers:

| Pointer | Starts at | Meaning |
|---|---:|---|
| `i` | `m - 1` | Last valid element in `nums1` |
| `j` | `n - 1` | Last element in `nums2` |
| `write` | `m + n - 1` | Position to fill next in `nums1` |

At every step, compare:

```python
nums1[i]
nums2[j]
```

Place the larger one at:

```python
nums1[write]
```

Then move the corresponding pointer left.

## Algorithm

Initialize:

```python
i = m - 1
j = n - 1
write = m + n - 1
```

While `j >= 0`:

1. If `i >= 0` and `nums1[i] > nums2[j]`, place `nums1[i]` at `nums1[write]`.
2. Otherwise, place `nums2[j]` at `nums1[write]`.
3. Move the pointer that supplied the value.
4. Move `write` left.

We only need to loop while `j >= 0`.

If `nums2` is fully copied, the remaining valid elements of `nums1` are already in the correct place.

## Walkthrough

Use:

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

Start:

```python
i = 2       # nums1[i] = 3
j = 2       # nums2[j] = 6
write = 5
```

Compare `3` and `6`.

Place `6` at the end:

```python
nums1 = [1, 2, 3, 0, 0, 6]
j = 1
write = 4
```

Compare `3` and `5`.

Place `5`:

```python
nums1 = [1, 2, 3, 0, 5, 6]
j = 0
write = 3
```

Compare `3` and `2`.

Place `3`:

```python
nums1 = [1, 2, 3, 3, 5, 6]
i = 1
write = 2
```

Compare `2` and `2`.

Since `nums1[i] > nums2[j]` is false, place `nums2[j]`:

```python
nums1 = [1, 2, 2, 3, 5, 6]
j = -1
write = 1
```

Now `nums2` is fully copied.

Stop.

The final array is:

```python
[1, 2, 2, 3, 5, 6]
```

## Correctness

The algorithm fills `nums1` from right to left.

At each step, `write` points to the largest still-empty position in the final merged array.

The largest remaining value must be either the last unused valid value of `nums1` or the last unused value of `nums2`, because both arrays are sorted.

So comparing `nums1[i]` and `nums2[j]` identifies the correct value for `nums1[write]`.

After placing that value, the algorithm moves the corresponding pointer left. The suffix after `write` is now correct and will never be changed again.

This invariant holds after every step: all positions to the right of `write` contain the largest already-merged values in sorted order.

When `nums2` has no remaining elements, every value from `nums2` has been placed. Any remaining values from the original valid part of `nums1` are already before `write` and already sorted. Therefore, the whole array is correctly merged.

## Complexity

Let:

```python
m = number of valid elements in nums1
n = number of elements in nums2
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(m + n)` | Each element is considered at most once |
| Space | `O(1)` | The merge uses only three pointers |

## Implementation

```python
class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        i = m - 1
        j = n - 1
        write = m + n - 1

        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[write] = nums1[i]
                i -= 1
            else:
                nums1[write] = nums2[j]
                j -= 1

            write -= 1
```

## Code Explanation

Start at the end of the valid part of `nums1`:

```python
i = m - 1
```

Start at the end of `nums2`:

```python
j = n - 1
```

Start writing at the final position of `nums1`:

```python
write = m + n - 1
```

The loop continues until all values from `nums2` are placed:

```python
while j >= 0:
```

If `nums1` still has values and its current value is larger, use it:

```python
if i >= 0 and nums1[i] > nums2[j]:
    nums1[write] = nums1[i]
    i -= 1
```

Otherwise, use the current value from `nums2`:

```python
else:
    nums1[write] = nums2[j]
    j -= 1
```

Then move the write pointer left:

```python
write -= 1
```

No return statement is needed because LeetCode checks the mutation of `nums1`.

## Testing

```python
def check(nums1, m, nums2, n, expected):
    s = Solution()
    s.merge(nums1, m, nums2, n)
    assert nums1 == expected

def run_tests():
    check([1, 2, 3, 0, 0, 0], 3, [2, 5, 6], 3, [1, 2, 2, 3, 5, 6])
    check([1], 1, [], 0, [1])
    check([0], 0, [1], 1, [1])
    check([2, 0], 1, [1], 1, [1, 2])
    check([1, 2, 4, 0, 0, 0], 3, [2, 3, 5], 3, [1, 2, 2, 3, 4, 5])
    check([-1, 0, 0, 3, 3, 3, 0, 0, 0], 6, [1, 2, 2], 3, [-1, 0, 0, 1, 2, 2, 3, 3, 3])

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 3]` and `[2, 5, 6]` | Main example |
| `nums2` empty | Nothing to merge |
| `nums1` has no valid elements | Copy all of `nums2` |
| Smaller `nums2` element | Confirms backward merge can overwrite placeholder correctly |
| Interleaved arrays | Checks normal merge behavior |
| Negative numbers and duplicates | Confirms sorted order with repeated values |