Two Pointers

Take "find two numbers summing to target" on a sorted array. Brute force checks all pairs — O(n²). But sorted order gives you leverage: the smallest element sits on the left, the largest on the right.

Stand one pointer at each end and look at their sum:

• Too small? The left value is too weak — and pairing it with anything other than the current maximum would be even smaller. Every pair involving it is ruled out. Move left inward.
• Too big? The right value is too strong by the mirror argument. Move right inward.

Each comparison permanently eliminates one element from consideration. n elements, n steps, done — O(n) where brute force needed O(n²).

The deep idea: sorted order means one comparison tells you about many pairs at once. You're not searching the n² grid of pairs; you're walking its boundary.

Principle: in sorted data, ask "what does this comparison let me discard?" If each step discards something for good, you've got a linear algorithm.

The skeleton you'll write a hundred times:

def pair_sum_sorted(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s == target:
            return [lo, hi]
        elif s < target:
            lo += 1      # nums[lo] can't partner with anyone — discard it
        else:
            hi -= 1      # nums[hi] is too big for everyone — discard it
    return [-1, -1]

The same converging skeleton powers a surprising range:

• Palindrome checks — compare ends, walk inward; any mismatch is fatal.
• Container with most water — move the shorter wall, because keeping it caps every future area it could form.
• 3Sum — fix one element, run converging pointers on the rest. One pattern nested inside a loop turns O(n³) into O(n²).

In every case the loop is mechanical; the interview content is the one-sentence proof of why the discarded element can never matter. Practice saying that sentence.

Converging pointers start at opposite ends. The other family starts both at the beginning and moves them at different speeds — a preview of patterns you'll meet again with linked lists and sliding windows.

The workhorse version is the reader/writer pass for in-place editing. write marks the boundary of the cleaned-up region; read scans ahead:

def dedupe_sorted(nums):
    write = 0
    for read in range(len(nums)):
        if read == 0 or nums[read] != nums[read - 1]:
            nums[write] = nums[read]
            write += 1
    return write   # first `write` slots hold the deduped prefix

Everything before write is final; everything between write and read is dead weight already processed. Remove-duplicates, move-zeroes, filter-in-place — all the same two-speed scan, all O(n) time, O(1) space.

The same different-speeds idea, run on a linked list (fast moves two hops per slow's one), finds middles and detects cycles — Floyd's tortoise and hare. You'll meet it properly in the linked-list week; recognize the family now.

Principle: two pointers means two frontiers — what's settled and what's being explored. Keep their invariant ("everything left of write is clean") in your head and the code writes itself.

Both kill the inner loop. How to pick:

The honest trade-off: two pointers is O(1) space but needs order — if you must sort first, you pay O(n log n) and lose original indices. Hashing is O(n) one-pass on any order but costs O(n) memory and won't naturally enumerate deduplicated combinations.

In an interview, naming this fork is the move: "unsorted, so a hash map gives one pass — but if it were sorted, two pointers would do it with no extra memory." One sentence, two patterns, full marks.

Principle: hashing buys speed with memory; two pointers buys speed with order. Identify which resource the problem hands you for free.