LC Patterns — Two / Three / N Pointers

Template 1 — Converge

left, right = 0, n - 1
while left < right:
    if condition(left, right):   # e.g., sum == target → found / record
        ...
    elif too_small(...):  left += 1     # only the limiting side moves
    else:                 right -= 1

Template 2 — Chase (reader/writer form)

write = 0
for read in range(n):            # read always advances; write only on keep
    if keep(nums[read]):
        nums[write] = nums[read]
        write += 1
return write                     # new logical length

Template 3 — Parallel

i = j = 0
while i < len(A) and j < len(B):
    if A[i] <= B[j]: consume A[i]; i += 1
    else:            consume B[j]; j += 1
# drain the leftover of whichever remains

Universal pitfalls

1. Moving the wrong pointer (or both at once) without a reason — the classic silent wrong answer. Decide which pointer is provably used up and move only that one.
2. Duplicate handling in k-sum: skip duplicates at every pointer level (while nums[i] == nums[i-1]: i += 1) — and only after recording a hit, or you'll skip the valid first occurrence.
3. left < right vs left <= right: finding a pair needs < (an element can't pair with itself); single-element checks (palindrome center) can use <=. Get this wrong and you either loop forever or miss the middle.
4. Forgetting to drain the leftover tail in parallel/merge patterns.
5. Sorting when you mustn't: if the answer needs the original indices (LC 1 Two Sum), sorting throws them away — use a hash map instead. Say the trade-off out loud: two pointers cost O(n log n) to sort but O(1) space; a hash map is O(n) time and space.
6. Linked-list null-safety: every fast.next.next needs fast and fast.next in the loop guard — recite the guard before you write the loop.

What it is: The array is sorted (or you sort it), and you want a pair with some property — a sum equal to a target, or a mirror check like a palindrome. Put one pointer at each end; each comparison tells you which side is "too small" or "too big," and that side steps inward.

Intuition: Say sum = arr[l] + arr[r]. If it's too small, then no pair using arr[l] can ever reach the target — every partner still available is ≤ arr[r], and that already wasn't enough. So arr[l] is used up: move l right. Too big is the mirror case: move r left. Every step throws away one element for good → O(n) after sorting. It's the same "prune what can't help" idea as binary search, but for pairs.

Approach: Template 1. For palindrome checks, the condition is s[l] == s[r], and both pointers move on a match. For strings with junk characters (non-alphanumerics), skip past those inside the loop.

What it is: Both ends still move inward, but the rule isn't a sorted sum — it's a bottleneck: the answer at any (l, r) is capped by the weaker side (shorter line, lower wall), so moving the stronger side can't possibly help, and you always advance the weaker one.

Intuition: Container With Most Water — the area is width × min(h[l], h[r]). If you move the taller side inward, the width shrinks and the height is still capped by the shorter side, so the area can only get worse. So the shorter side is the one holding you back: move it, hoping to find a taller wall. Trapping Rain Water extends this with running maxima: whichever side has the smaller max so far is fully decided ("water here = maxLeft − height"), so lock it in and advance it.

Approach: Template 1, where the move rule is "advance the pointer with the smaller height/value," usually while carrying best, max_left, max_right accumulators. For pairing problems (boats): greedily put the heaviest with the lightest; if they don't fit together, the heaviest goes alone.

What it is: Find triplets/quadruplets that sum to a target: sort the array, pin the first element with an outer loop, and solve the remaining pair with Pattern 1's converge inside. 4Sum pins two elements, kSum recurses down to 2Sum — so "N pointers" is really "N−2 pinned loops + one converge."

Intuition: Sorting buys two things at once: the two-pointer sum walk and easy duplicate-skipping (equal values sit next to each other). The recursion: kSum(target) = for each pin i, solve (k−1)Sum(target − nums[i]) — the base case 2Sum is the only place pointers actually move.

Approach: sort → for i (skip dups: if i > 0 and nums[i] == nums[i-1]: continue) → converge l = i+1, r = n-1 → on a hit, record it and skip duplicates on both l and r, then move both. Prune: break when nums[i] * k > target (even the smallest possible sum is already too big). O(n^(k−1)).

What it is: Remove or rearrange elements in place with O(1) extra space: one pointer reads every element, a second (always ≤ the reader) marks where the next "kept" element goes. Everything before the writer is the answer-so-far; the function returns the writer as the new length.

Intuition: The invariant does all the work: [0, write) is exactly the kept region, [write, read) is garbage you're free to overwrite. The reader advances every step, the writer only on keeps — so the writer never overtakes the reader and no kept data is ever clobbered. This is compaction, the same trick garbage collectors and log compaction use.

Approach: Template 2. Variants: "at most k duplicates" → keep if nums[read] != nums[write-k]; "move zeroes preserving order" → write the non-zeros, then either fill the tail with zeros or swap-on-write to keep the values.

What it is: Two pointers race through a linked structure — slow moves 1 step, fast moves 2. If there's a cycle they must meet inside it; if not, fast runs off the end (null). A second phase (reset one pointer to the head, move both at speed 1) finds the exact spot where the cycle begins.

Intuition: Inside a cycle, fast gains exactly 1 node on slow every step, so it can't jump over slow — they're guaranteed to land on the same node within one lap. Phase 2 is a little algebra: at the meeting point, the distance from the head to the cycle start equals the distance from the meeting point to the cycle start (2(a+b) = a+b+c+b ⇒ a = c) — memorize that two-line derivation, interviewers ask for it. The big generalization: any repeated function x → f(x) on a finite set is secretly a linked list — that's how 287 (the array is i → nums[i]) and happy-number turn into cycle problems.

Approach: while fast and fast.next: → advance; if slow == fast: cycle found. Then reset one pointer to the head and walk both at speed 1 until they meet — that's the entry. For 287: f(i) = nums[i], and the duplicate value is the cycle entry.

What it is: Find a spot in a singly linked list you can't index into — the middle, or the k-th from the end — in a single pass. Either give one pointer a k-node head start (then move both until the leader hits the end), or use speeds 1 and 2 so the slow pointer lands in the middle when fast finishes.

Intuition: A fixed head start is preserved as both pointers move at the same speed — so when the leader reaches the end, the trailer is exactly k behind it, no length count needed. Speed 2-vs-1 means slow covers half of whatever fast covers: fast at the end ⇒ slow at the middle. These combine into recipes: "is this list a palindrome" = find the middle (this pattern) + reverse the second half + compare in parallel (Pattern 7).

Approach: gap-K: advance lead k steps (often from a dummy node, so "delete the k-th from end" leaves you just before the target); then move both to the end. Midpoint: while fast and fast.next: slow = slow.next; fast = fast.next.next.

What it is: One pointer per sequence; at each step, compare the two current elements and advance the pointer whose element you just used. This is the merge step of merge-sort, generalized: merging, intersecting, or comparing two sorted (or independently walkable) sequences in O(m+n).

Intuition: Sortedness means the smaller current element can't match or beat anything further along in the other sequence — so use it now and move on. The famous twist for in-place merge (88): merge backwards, largest first — the free space is at the end of the target array, so writing the biggest values there never overwrites an element you haven't read yet.

Approach: Template 3 + drain the leftover. Variants: intersection (advance the smaller, record equals), backspace-compare (walk both backwards, resolving #s with a skip counter before each comparison — going backwards turns "look ahead" into "look behind").

What it is: The opposite of converge: the pointers start together and move outward. Every palindrome has a center, so try all 2n−1 centers (each character, and each gap between two characters) and expand l--, r++ while the characters match.

Intuition: A palindrome is fully described by its center + how far it reaches, so listing every center covers every palindrome exactly once, and expansion stops at the first mismatch (you get the longest one for free). 2n−1 centers × O(n) expansion = O(n²) with O(1) space — the sweet spot between brute force O(n³) and Manacher's O(n) (name-drop Manacher; never code it live).

Approach: for each i: expand from (i, i) (odd-length) and from (i, i+1) (even-length); track the best window, or count every successful expansion (647 counts each expansion step, not just the maximal one).

What it is: Split an array into three regions in one pass with three pointers: low (edge of the 0-region), mid (the scanner), high (edge of the 2-region). Classic form: sort an array of 0s/1s/2s in place, without counting.

Intuition: Keep four zones by invariant: [0, low) = 0s, [low, mid) = 1s, [mid, high] = unknown, (high, n) = 2s. Every scanner step shrinks the unknown zone by at least one, from one side or the other → O(n), one pass. This is quicksort's 3-way partition; knowing that connection answers "where would you use this in real life?" (sorting data with lots of equal keys).

Approach: mid scans: on 0 → swap into low, advance both; on 1 → just mid++; on 2 → swap into high, high--, and do not advance mid (the element that just arrived from high hasn't been examined yet). Two-way (parity/binary) partitions are the degenerate case (simple reader/writer or converge-swap).

What it is: Check whether string s is a subsequence of t (same characters in order, gaps allowed): one greedy pointer per string, always advance t's pointer, advance s's only on a match; if s runs out, it's a subsequence. Extends to "which of many candidate words fit inside t."

Intuition: Greedy matching is safe by an exchange argument: matching each character of s at the earliest place it can go in t never hurts — any later match could be swapped for the earlier one. This is Pattern 7's parallel topology, where one sequence is the filter and only one pointer's advance is conditional.

Approach: two pointers, O(m+n) per check. The follow-up that levels you up (asked in 392): many queries against the same t → preprocess t into "char → sorted list of positions," then each query character binary-searches the next usable position (binary search Pattern 2 — the series composes). For 524, run the check per candidate, tracking longest-then-lexicographically-smallest.