> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Merge Sorted Array Python Solution with Tests

> Tested Python solution for LeetCode 88 with 18 pytest cases. Generate a practice environment with lcpy.

LeetCode 88, Easy. Topics: Array, Two Pointers, Sorting. [View on LeetCode](https://leetcode.com/problems/merge-sorted-array/description/).

Generate this problem as a practice environment: tested reference solution, 18 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 88   # by problem number
lcpy gen -s merge_sorted_array   # by problem name
```

## Problem

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

### Examples

```
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 \[\<u>1\</u>,\<u>2\</u>,2,\<u>3\</u>,5,6], with the underlined elements coming from nums1.

```
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].

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

### Constraints

* nums1.length == m + n
* nums2.length == n
* 0 \<= m, n \<= 200
* 1 \<= m + n \<= 200
* -10^9 \<= nums1\[i], nums2\[j] \<= 10^9

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

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/merge_sorted_array/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/merge_sorted_array/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
class Solution:
    # Time: O(m + n)
    # Space: O(1)
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        # Fill from the back to avoid overwriting nums1's real elements
        index = m + n - 1
        i = m - 1
        j = n - 1

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

        # Only nums2 leftovers can remain
        while j >= 0:
            nums1[index] = nums2[j]
            j -= 1
            index -= 1
```

## Complexity

| Time     | Space |
| -------- | ----- |
| O(m + n) | O(1)  |

## Tags

[NeetCode 250](/catalog/neetcode-250), [NeetCode All](/catalog/neetcode).