Loading...
Tier I · Fundamentals
Walking a sequence from both ends or in tandem to avoid nested loops.
Two indexes walk the same array at once. Because each one only moves forward, the whole scan finishes in one pass instead of a nested loop, with no extra memory.
Sorted array, target 15. Start with L at the smallest value and R at the largest.
Watch the two ends walk inward. Each step rules out one value for good, so the pair turns up without ever checking every combination.
| Variant | How the pointers move | Typical use |
|---|---|---|
| Converging | From both ends toward the middle | Pair sums, palindromes, container water |
| Read / write | Both left to right, the writer lags | Compacting or filtering in place |
| Fast / slow | Same direction, one twice as fast | Cycle detection, finding the middle |
Converging pointers usually need a sorted array, because moving a pointer has to be a safe decision: on a sorted array, a pair sum that is too small can only be fixed by moving the left pointer right. Read/write and fast/slow pointers do not need a sort.
| Approach | Time | Extra space |
|---|---|---|
| Nested loop over all pairs | ||
| Sort, then two pointers | ||
| Two pointers on sorted input |
Use it when the array is sorted, or when the task is about positions: reversing, compacting, partitioning, or pairing elements from the two ends.
The problems below start with a palindrome check and in-place compaction, move through pairing on sorted arrays, and end with three-way partition and trapping water.