Sliding Window
Keep a moving range over your data and update its summary in place — one pass instead of many.
Prerequisites
- Big-O & Asymptotic Analysis — we're killing an
O(n²)scan of subarrays. - Two Pointers — a sliding window is two pointers glued to a contiguous range.
- Strings — "longest substring" problems live here.
The 10-second version
A sliding window keeps a moving range [left, right] over an array or string and maintains a
running summary of what's inside it — a sum, a count, a character set. As the range slides,
you fold in the one element that enters and remove the one that leaves, instead of recomputing
the range from scratch. With a fixed size you slide by adding one and dropping one. With a
flexible size you grow the right edge while a constraint holds and shrink the left edge when it
breaks. Either way it's a single pass: O(n).
Why this existed
The name is older than the algorithm. "Sliding window" was coined in networking and signal processing, where you constantly need a summary of the recent past — the last N packets, the last few seconds of samples — and you can't afford to recompute it every tick.
- 1931 — Walter Shewhart's control charts smooth noisy measurements over a rolling window of recent samples. The moving average is the original sliding window.
- 1974 — Vint Cerf and Bob Kahn's paper on internetworking describes TCP's sliding window protocol, which tracks a moving range of in-flight data for flow control. This is where the phrase enters computing for good.
- 1980s onward — the idea escapes the wire and lands in algorithms: any "contiguous subarray / substring with a constraint" problem becomes a window you slide.
Why it mattered: the whole world is a stream. Logs, prices, packets, sensor readings — they arrive one at a time, and every interesting question is about a recent stretch of them. Recomputing that stretch from scratch turns a real-time system into a batch job. The sliding window is what keeps it real-time.
Inside the inventor's head
Look at the problem pattern that forces the trick. You want the longest substring with no
repeated character, or the largest sum of k consecutive values, or the shortest window whose
sum reaches a target. They're all one family: a contiguous range with a constraint.
The straightforward attack enumerates every range. For each start i, extend the end j and
check the constraint:
// brute force: try every substring, test for repeats — very slowfunction longestNaive(s) { let best = 0; for (let i = 0; i < s.length; i++) { for (let j = i; j < s.length; j++) { const seen = new Set(); let ok = true; for (let k = i; k <= j; k++) { if (seen.has(s[k])) { ok = false; break; } seen.add(s[k]); } if (ok) best = Math.max(best, j - i + 1); } } return best;}That's O(n³) when you re-check the whole substring. The first instinct is to fix that inner
re-check by keeping a set as you extend j — dropping to O(n²). Better, but still quadratic
because for every new start you rebuild the set from nothing.
The pivot is noticing what actually changes when the window slides by one position.
Two insights land together. First: incrementality — update the summary by the delta, not from scratch. Second: monotonicity — because of how the constraint behaves, the left edge never has to jump backwards. Together they mean each index is added once and removed once, so the total work is linear. That's the entire window.
The final approach
Fixed vs variable windows
There are two shapes, and picking the right one is half the battle.
- Fixed window (size
kknown up front): add the entering element, subtract the leaving one. Moving average, max sum ofkconsecutive items, rate per fixed interval. - Variable window (constraint, size unknown): advance
right; while the window violates the constraint, advanceleft; record the best valid window.
The variable version is the one that surprises people, so let's make it precise.
Why the window never needs to shrink-then-regrow
This is the question that stops most people, so here it is head-on. When you add a new right
element and the window breaks, you shrink from the left until it's valid again. Why can't you
ever need to push left back to the right and re-explore?
Because for these constraints validity is monotone: if a window is valid, then every window
inside it is also valid. (A substring with no repeats contains no substring with a repeat; a
window whose sum is under budget contains only smaller-sum windows.) So once a particular left
boundary has been abandoned, no larger window starting before it — and ending at the current
right or later — could possibly be valid either. The left edge is non-decreasing, and that
is the whole reason the loop is linear: right sweeps n times, and left sweeps n times
in total, never rewinding.
The invariant
- Non-decreasing left.
leftonly ever increases across the whole run. - Validity on record. After the shrink loop,
[left, right]always satisfies the constraint. - No missed answer. For each
right, the best valid window ending there is the longest one, which starts at the currentleft. We record its length before advancing.
A worked trace
Longest substring without repeating characters, on "abcabcbb":
right | char | seen before? | left after | window | length | best |
|---|---|---|---|---|---|---|
| 0 | a | no | 0 | a | 1 | 1 |
| 1 | b | no | 0 | ab | 2 | 2 |
| 2 | c | no | 0 | abc | 3 | 3 |
| 3 | a | yes, at 0 | 1 | bca | 3 | 3 |
| 4 | b | yes, at 1 | 2 | cab | 3 | 3 |
| 5 | c | yes, at 2 | 3 | abc | 3 | 3 |
| 6 | b | yes, at 4 | 5 | cb | 2 | 3 |
| 7 | b | yes, at 6 | 7 | b | 1 | 3 |
Answer: 3 ("abc"). Note left went 0,0,0,1,2,3,5,7 — it budged forward eight times
across the whole scan, never backward.
It in code
function lengthOfLongestSubstring(s) { const last = new Map(); let best = 0, left = 0; for (let right = 0; right < s.length; right++) { const c = s[right]; if (last.has(c) && last.get(c) >= left) left = last.get(c) + 1; // jump past it last.set(c, right); best = Math.max(best, right - left + 1); } return best;}The fixed-window shape
When the size is known, the window doesn't need a validity check at all — it just slides.
function maxWindowSum(a, k) { let window = 0; for (let i = 0; i < k; i++) window += a[i]; let best = window; for (let i = k; i < a.length; i++) { window += a[i] - a[i - k]; // one enters, one leaves best = Math.max(best, window); } return best;}Cost
| Aspect | Cost | Why |
|---|---|---|
| Time — best | O(n) | it's always a single pass |
| Time — average | O(n) | each index enters and leaves once |
| Time — worst | O(n) | left moves at most n times in total |
| Space — fixed window | O(1) | just the running aggregate |
| Space — variable window | O(k) | a set/map of the current window |
Where you meet it today
- Networking. TCP flow control is literally a sliding window over the sequence of bytes in flight — the original meaning of the term.
- Monitoring dashboards. "Requests per minute," "average latency over the last 60s," and every rolling metric is a fixed window being updated by the delta.
- Rate limiting. A sliding-window counter admits a request only if the recent window is under budget — the exact variable-window shape.
- Streaming analytics. Longest streak, moving median, peak burst: all one pass with a window.
// timestamps sorted ascending; busiest window of width wfunction maxRequestsInWindow(ts, w) { let best = 0, left = 0; for (let right = 0; right < ts.length; right++) { while (ts[right] - ts[left] >= w) left++; best = Math.max(best, right - left + 1); } return best;}Recap
- A sliding window is a contiguous range with a running summary, updated by the delta (one in, one out) instead of recomputed.
- Fixed windows slide by size; variable windows grow on the right and shrink on the left to satisfy a constraint.
- The window is
O(n)because validity is monotone: the left edge never moves backward and each index enters and leaves once. - Store
O(1)state for fixed windows,O(k)for variable ones.
Next up: Prefix Sums & Difference Arrays — when the range
start jumps around instead of sliding, precompute once and answer in O(1).