Merge Sorted Array

Intuition

The simplest correct idea ignores that both inputs are already ordered. Copy every element of the second array into the trailing placeholder slots of the first, so the first array now holds all m + n values in some order. A single sort then puts everything in non-decreasing order. It wastes the pre-sorted structure but is easy to reason about and hard to get wrong.

Algorithm walkthrough

1. 1Copy the n values from the second array into positions m through m + n - 1 of the first array.
2. 2Sort the entire first array.
3. 3The first array now contains all values in sorted order.

Implementation

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        for i in range(n):
            nums1[m + i] = nums2[i]
        nums1.sort()

Intuition

Writing from the front would overwrite values we still need, so instead fill from the back where the free placeholder slots already sit. Keep a pointer at the last real element of each array and a write pointer at the very end of the first array. At each step, compare the two candidates and copy the larger one into the write slot, stepping that pointer back. Because we always take the biggest remaining value and place it at the highest unfilled position, nothing important is ever clobbered, and the merge finishes in a single reverse pass.

Algorithm walkthrough

1. 1Set i to the last real index of the first array (m - 1), j to the last index of the second (n - 1), and k to the final slot (m + n - 1).
2. 2While elements remain in the second array, compare nums1[i] with nums2[j].
3. 3Copy the larger of the two into position k, then move that source pointer and k backward.
4. 4If the first array runs out (i < 0), the remaining second-array values simply flow into place.
5. 5Once j drops below zero, any leftover first-array values are already in their correct positions.

Implementation

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        i = m - 1
        j = n - 1
        k = m + n - 1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1