:orphan:

Merge Sorted Array
==================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/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.

 

**Constraints:**

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

 

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

.. highlight:: python

Pattern
-------
Array, Two Pointers, Sorting

Solution
--------
To merge 2 sorted lists, pick the least element from the 2 lists and add
it to the result. Repeat until both of the input lists are empty. However, here
the result list is ``nums1``. Naively merging the lists into ``nums1`` would
overwrite entries in ``nums1`` that we still need to compare. To get around this,
shift the entries in ``nums1`` to the end of the list, and then merge the lists.

Code
----

.. literalinclude:: ../problems/easy/merge-sorted-array/merge_sorted_array__approach_1.py
    :language: python
    :lines: 20-

Test
----
>>> from merge_sorted_array__approach_1 import merge
>>> nums1 = [1, 2, 3, 0, 0, 0]
>>> nums2 = [2, 5, 6]
>>> merge(nums1, 3, nums2, 3)
>>> nums1
[1, 2, 2, 3, 5, 6]
>>> nums1 = [1]
>>> nums2 = []
>>> merge(nums1, 1, nums2, 0)
>>> nums1
[1]
>>> nums1 = [0]
>>> nums2 = [1]
>>> merge(nums1, 0, nums2, 1)
>>> nums1
[1]

Complexity
----------
| :math:`m` is the length of the first input list and :math:`n` is the length of the second input
| Time: :math:`O(m + n)` — shift the first list and then merge the two lists
| Auxiliary Space: :math:`O(1)` — in-place merge

.. autofunction:: merge_sorted_array__approach_1.merge