What is a Sliding Window?
A sliding window keeps information about one contiguous range while its boundaries move through the input. It avoids recalculating almost the same range again and again.
You need array or string indexes, running totals, and frequency maps. The short version is: reuse the previous range by adding what enters and removing what leaves.
The Core Idea: Update the Range
In LC 643: Max Subarray Sum (k=3), the values are [2,1,5,1,3,2].
The first window sum is 2 + 1 + 5 = 8.
How do we find the next window sum? We remove 2, add the next 1, and get 7. There is no reason to add the shared values 1 and 5 again.
It is like viewing a street through a train window. As the train moves, one building leaves the view and one new building enters.
How a Fixed Window Slides
The Rule You Keep True
The running state must equal the sum, counts, or other summary of exactly the elements from left through right.
When a boundary moves, the state changes before the next answer is measured.
The boundary rule changes by problem:
- Fixed-size window keeps length exactly
k. - Longest valid window expands right and shrinks only when invalid.
- Shortest valid window shrinks repeatedly while the condition remains valid.
- Budget window tracks how many replacements or violations are currently used.
Minimum Window Substring is the one that usually trips us up. The right boundary first makes the window valid, but the answer may still contain unnecessary characters. We must shrink from the left while every required count remains satisfied.
Picking the Right Shape
From Rule to Code
- Define what the window state stores and what makes a window valid.
- Move
rightforward and add the entering value. - Shrink from
leftas often as the problem's rule requires. - Update the answer only when the current window has the required shape.
- Remove each leaving value before moving
leftpast it.
Both boundaries move only forward, so the scan takes O(n) time plus the space required by the window state.
When to use it
- •The answer concerns a contiguous part of an array or string.
- •Neighboring candidate ranges share most of their elements.
- •A window can be updated by adding one item and removing another.
- •A condition tells an adjustable left boundary when to shrink.
How to identify it
- •The prompt asks for a longest, shortest, maximum, or count over contiguous elements.
- •The input is scanned from left to right while a recent range stays active.
- •Recomputing each range would repeat almost all of the previous work.
- •The active range can be summarized by a sum, frequency map, or count of violations.
Key insights
- →A window is the inclusive range between `left` and `right`.
- →Fixed windows remove one left item whenever one right item is added after reaching size `k`.
- →Variable windows expand right and shrink left until their condition becomes valid again.
- →The maintained state must describe exactly the elements currently inside the window.
- →Each boundary moves forward at most `n` times, so a nested-looking shrink loop can still be linear.
Common mistakes
- 01Using a sliding window when negative values make the condition non-monotonic.
- 02Updating the answer before the window has reached the required size.
- 03Moving `left` without removing its value from the running state.
- 04Shrinking only once when several removals are needed to restore validity.
- 05Confusing window length `right - left + 1` with `right - left`.