All patterns
Two Pointers
Walk two indices through the data so nothing is scanned twice.
time O(n) after sortingspace O(1)
What it is
Keep two indices, usually at opposite ends or moving in the same direction, and move them by rule instead of testing every pair. Each pointer only moves one way, so the total work is linear.
When to reach for it
- Sorted array or string and you need a pair, triple or partition
- In-place removal, dedupe or reordering
- Palindrome or symmetric checks
- Merging two sorted sequences
Clues in the problem
- “Find two numbers that…” on sorted input
- Asked for O(1) extra space
- Brute force is a nested loop over i < j
Template
def two_pointers(a, target):lo, hi = 0, len(a) - 1while lo < hi:s = a[lo] + a[hi]if s == target:return lo, hiif s < target:lo += 1 # need a bigger sumelse:hi -= 1 # need a smaller sumreturn None
Practice problems
- Two Sum II (sorted)
- 3Sum
- Container With Most Water
- Remove Duplicates from Sorted Array
- Valid Palindrome
Common mistakes
- Using it on unsorted data without sorting first
- Moving both pointers when only one should move
- Off-by-one on lo < hi versus lo <= hi