LeetCode 88 · Two pointers

Merge Sorted Array, explained with a picture

Filling a parking row from the back.

Two pointers
▶ Watch it step by step

The problem

Merge sorted list B into sorted list A, which has empty space at its end. Do it in place.

Input:  A = [1, 2, 3, _, _, _], B = [2, 5, 6]
Output: [1, 2, 2, 3, 5, 6]

Picture it

Picture filling a parking row from the back. Compare the last real car of A with the last of B and park the bigger one in the last empty slot. Filling from the back means we never overwrite a car we still need.

Short version: the full lesson (brute force, complexity, edge cases and a quiz) is still being written. The animation is complete.

The key idea

Three pointers from the end. O(m + n).

Python solution

def merge(a, m, b, n):
    i, j, k = m - 1, n - 1, m + n - 1
    while j >= 0:
        if i >= 0 and a[i] > b[j]:
            a[k] = a[i]; i -= 1
        else:
            a[k] = b[j]; j -= 1
        k -= 1

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.