CONCEPT · Pupil
Two pointers
also opposite ends · inchworm
Walk two indices with a monotonic invariant so each element is processed O(1) times. Linear after a possible sort.
Intuition
If moving a pointer backwards cannot help, never do it. That refusal is the speedup.
When to reach for it
- Pair sum on a sorted array
- Containers with water
- Merging two sorted lists
Usual pits
- Applying the sorted move rule to an unsorted array
- Infinite loops when you forget to increment