Lesson 6 — Two pointers, converging

~20 minutes · Day 4 · two pointers from the end · Python

Tonight's problem is Merge Sorted Array. Interviewers like it because the hard part is not merging two sorted lists. The hard part is doing it inside the first array without destroying values you still need to read.

The invariant

Fill from the end with two pointers walking inward, so you never overwrite a value you still need.

That's the whole pattern. If the empty space is at the back, the safe direction is backward. Compare the largest remaining values, write the larger one into the final open slot, then move inward.

The read pointers look at the largest remaining values, while the write pointer protects the unread front of nums1.

Merge Sorted Array: the slow way first

The LeetCode statement gives two sorted arrays. The first array, nums1, has m real values followed by n placeholder slots; nums2 has n real values. The direct baseline is: copy nums2 into those slots, then sort the whole list. Python's list.sort sorts a list in place, and the Python wiki lists sorting as O(n log n) work (Python wiki: time complexity).

def merge(nums1, m, nums2, n):
    nums1[m:] = nums2[:n]       # put nums2 into the spare slots
    nums1.sort()                # correct, but spends sorting time

This works, but it ignores the strongest fact in the problem: both real parts are sorted. A standard merge can combine sorted inputs in linear time (Wikipedia: merge algorithm). The only trap is writing from the front: if nums2[0] is small, writing it at nums1[0] would erase a value from nums1 before it has been compared.

Merge Sorted Array: the backward way

Start two read pointers at the last real values: i = m - 1 for nums1 and j = n - 1 for nums2. Start the write cursor at the last slot: write = m + n - 1. Each step writes the larger remaining value.

def merge(nums1, m, nums2, n):
    i = m - 1                         # last real value in nums1
    j = n - 1                         # last value in nums2
    write = m + n - 1                 # last open slot in nums1
    while j >= 0:
        if i >= 0 and nums1[i] > nums2[j]:
            nums1[write] = nums1[i]   # keep the larger tail value
            i -= 1
        else:
            nums1[write] = nums2[j]   # copy nums2's tail value
            j -= 1
        write -= 1                    # next slot moves left

The loop only needs to continue while nums2 still has values. If nums1 has leftover values, they remain in the correct left-side positions.

Transfer: same pattern, new costume

Suppose a log system keeps main = [2, 4, 9, 0, 0, 0] with three real entries, and receives extra = [1, 6, 8]. It must merge extra into main without another array. Before opening the answer: what should be compared first, and where should the first write happen?

What the trade buys you

The win is not clever syntax. It is choosing the direction that protects unread values.

Practice — answer before you scroll past

i = m - 1
j = n - 1
write = 0

Your move (tonight)

Solve Merge Sorted Array in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Predict: say the copy-then-sort baseline and the backward invariant out loud.
2. Attempt: write the in-place version with i, j, and write.
3. Compare: watch the source below only after your attempt.
4. Encode: write the invariant in your own words in Notes.

Stuck or curious? Ask your teacher (the agent) — that's what it's for.