The idea
Many brute-force solutions try every start l and every end r: O(n²). If moving l to the right never forces r to move back, both pointers sweep the array once and the work drops to O(n).
Two common shapes: a sliding window (both pointers move the same way) for the longest or shortest subarray under a constraint, and two ends moving inward on a sorted array for pair sums.
The technique is valid only when the condition is monotone: for example, with non-negative values, a longer window never has a smaller sum.
Sample problem
209. Minimum Size Subarray Sum ↗ Medium
Given an array of positive integers and a target, return the length of the shortest contiguous subarray whose sum is at least the target, or 0 if there is none.
target = 7, nums = [2,3,1,2,4,3] output = 2 ([4,3])
Why the solution works
All numbers are positive, so a window’s sum grows when it is extended and falls when it is shrunk. That monotonicity is what two pointers need.
Move r one step at a time. Whenever the window reaches the target, record its length and shrink from the left while it still qualifies: a shorter valid window ending at r can only start further right.
l never moves back, because a start that was too far left for an earlier r is also too far left for a later one.
Complexity: O(n) time: l and r each move at most n steps. O(1) memory.
Watch out
- Check monotonicity first. With negative numbers a sum window is not monotone and the method breaks.
- Update the answer at the right moment: after extending, before shrinking.
- Handle the case where a single item does not fit, so l does not overtake r incorrectly.