Sliding window technique

In short: The sliding window pattern moves a “window” across a sequence and updates its value only at the edges instead of recomputing it each time.

In more detail: Instead of re-adding all k elements for each position, you subtract the element that falls out and add the one that comes in. O(n·k) becomes O(n).

In Depth

• Fixed window: For example the largest sum of k consecutive numbers.
• Variable window: The right edge grows, the left edge catches up as soon as a condition is violated (for example “longest substring without repeats”).
• Helpers: A hash table counts characters in the window, a deque gives the maximum in the window.
• Recognizing it: Questions about a “contiguous segment” with sum, length or count are typical candidates.
• Related: The two-pointer technique.

See also: Two-pointer technique and sliding window