A window over a sequence
The sliding window technique answers questions about contiguous subarrays or substrings by maintaining a range with two pointers, a left and a right. Instead of recomputing each candidate range from scratch, you adjust the window incrementally as it slides forward.
Two flavors
- A fixed size window always spans the same width. As the right pointer advances by one, the left pointer follows by one, and you update a running aggregate by adding the entering element and removing the leaving one.
- A variable size window grows by moving the right pointer until a constraint breaks, then shrinks by moving the left pointer until the constraint holds again. This finds the longest or shortest range meeting a condition.
Why it is efficient
Each pointer only ever moves forward, so across the whole run each element enters and leaves the window at most once. The total movement is linear even though the window itself constantly resizes. The key requirement is that the constraint behaves monotonically as the window grows or shrinks.
Key idea
Slide a two pointer window forward, updating the aggregate incrementally, so each element is processed a constant number of times and the whole scan stays linear.