Two monotonic pointers can replace a nested search with a linear scan. The key is proving that discarded positions never need to be revisited.
A simulator showing how two pointers eliminate candidates
Choose a mode and change the target. Faded cells have been eliminated from consideration.
Converging pointers
If the pair sum is too small, advance l; if too large, retreat r. When even the largest remaining partner cannot help a[l], that left value is safely discarded. This argument requires a sorted array.
Move in the same direction
Expand with r and shrink with l when the sum condition is met. Positive values ensure that expansion increases the sum and contraction decreases it. Negative values break this monotonicity; exact-sum counting can instead combine Prefix sums with hashing, while shortest-threshold problems may need other techniques.
Common coding exercises
Common patterns include sorted pair sum, fixing one value then solving three-sum in O(n²), merging sorted arrays, shortest positive subarray above a threshold, and minimum pair difference meeting a lower bound.