Two Pointers — How the Pattern Works
The Two Pointers pattern coordinates two (or occasionally three) index or node references across one or two linear structures according to a deterministic movement rule. At every iteration, a structural invariant — such as sorted monotonicity, mirror symmetry, a fixed pointer gap, or a read/write partition boundary — guarantees that advancing a pointer permanently discards candidate states that cannot form a valid or optimal solution. This state-space pruning collapses nested O(n^2) brute-force searches or multi-pass copies into a single O(n) scan (or O(n log n) when sorting first) while typically requiring only O(1) auxiliary space.
- Pair, triplet, or pair-counting problems on a sorted (or sortable) array where shifting left or right endpoints monotonically increases or decreases a sum.
- Palindrome checks, 180-degree digit rotations, or sequence/substring reversals that compare or swap mirrored indices (i, n - 1 - i) from both ends inward.
- In-place array filtering, deduplication, run-length compression, or 3-way partitioning where a write pointer trails a read scanner without allocating a copy.
- Single-pass linked list or parent-pointer tree problems requiring a fixed k-node offset from the tail or path-length equalization via head switching.
- Synchronized traversal across two strings or sorted arrays — including subsequence matching, alternating or monotonic merges, word abbreviations, and chunked version comparisons.
- Off-by-one loop termination (
left < rightvs.left <= right): pair searches require two distinct indices (left < right), whereas self-symmetric center validation (Strobogrammatic Number) or unclassified middle regions (Sort Colorswithmid <= high) must evaluate the meeting index. - Advancing
midafter swapping withhighin 3-way partitioning (Sort Colors): the value swapped in fromnums[high]has not been inspected yet, so onlyhighshould decrement on that branch. - Testing value equality (
!=) instead of object identity (is not) on linked list or tree nodes (Intersection of Two Linked Lists,Lowest Common Ancestor III), which terminates prematurely on distinct nodes sharing duplicate values. - Violating sorted or non-overtaking invariants: read/write deduplication misses non-adjacent duplicates if the input is unsorted, and in-place string encoding is safe only when encoded output never exceeds the consumed input length.
def two_pointer_converge(nums, target):
left, right = 0, len(nums) - 1
while left < right:
curr = nums[left] + nums[right]
if curr == target:
return [left, right]
if curr < target:
left += 1
else:
right -= 1
return [-1, -1]def compact_in_place(nums, should_keep):
write = 0
for read in range(len(nums)):
if should_keep(nums[read], write, nums):
nums[write] = nums[read]
write += 1
return writedef walk_two_sequences(seq1, seq2):
i = j = 0
while i < len(seq1) and j < len(seq2):
if seq1[i] == seq2[j]:
i += 1
j += 1
else:
j += 1
return i == len(seq1)def equalize_paths(head_a, head_b):
a, b = head_a, head_b
while a is not b:
a = a.next if a else head_b
b = b.next if b else head_a
return a