What this module covers: Module F-7's moving average already hinted at this: instead of recomputing a result from scratch for every possible subarray or substring, maintain a "window" and adjust it incrementally as it moves. This module formalizes that into two variants — a fixed-size window and a variable-size window that expands and contracts based on a constraint — both of which turn an O(n × k) or O(n²) brute force into O(n).
The Problem: Recomputing From Scratch Is Wasteful
Say you need the maximum sum of any 3 consecutive elements in an array. The direct approach checks every possible window of size 3, summing each one independently:
typescript
Every window shares k - 1 elements with the window right before it — only one element enters and one leaves as the window slides forward by one position. Recomputing the full sum from scratch throws away that overlap and redoes work you already did one step ago.
Fixed-Size Window: Maintain a Running Total
The fix mirrors Module F-7's moving average exactly: keep a running sum, add the new element entering the window, subtract the element leaving it.
typescript
The first window is summed once, up front. Every window after that costs exactly one addition and one subtraction, regardless of k — the window "slides" one position at a time instead of being recomputed. This is the same window-shift math as the queue's moving average in Module F-7, applied to arrays directly instead of a live stream.
Analogy: A sliding window is a physical picture frame moving across a long mural, one step at a time. You don't repaint what's inside the frame every time you move it — you just note what came into view on one edge and what fell out of view on the other.
Variable-Size Window: Expand and Contract on a Constraint
Not every problem has a fixed window size — often the window needs to grow while some condition holds, and shrink the moment it's violated. The classic example: the longest substring with no repeating characters.
typescript
right only ever moves forward, one step per outer-loop iteration. left also only ever moves forward, and — this is the part worth checking carefully — across the entire run, left can advance at most s.length times in total, even though it's inside a while loop nested inside the for. That's the same "bounded total work across the whole run, despite looking nested" reasoning from the monotonic stack in Module F-6: neither pointer ever moves backward, so the combined work is O(n), not O(n²).
The general shape, worth recognizing whenever you see "longest/shortest substring or subarray satisfying some condition":
Expand the window by moving right forward and incorporating the new element.
While the window violates the constraint, shrink it by moving left forward and removing elements.
After each step, the current window is valid — record it if it's the best seen so far.
This same shape solves "longest substring with at most K distinct characters" (shrink when distinct count exceeds K, tracked with a frequency map from Module F-4) and "smallest window containing all characters of a target string" (shrink while the window still satisfies the containment condition, tracking the smallest valid window found) — different constraints, identical expand/contract skeleton.
Why This Beats Recomputing
Compare the two approaches directly: the brute-force fixed-window version does O(k) work for each of roughly n starting positions — O(n × k) overall. The variable-window version does O(1) amortized work per step of right, because left never revisits ground it's already covered. Both versions are asymptotically better than the naive "check every possible substring/subarray" approach, which is O(n²) or worse before you even account for the cost of evaluating each candidate.
Where This Shows Up in Your Stack
Rate limiting: "how many requests has this client made in the last 60 seconds?" is a sliding time window over a stream of timestamps — old timestamps fall out of the window exactly the way s[left] gets removed above, without rescanning the whole request history on every check.
Time-series aggregation: "average CPU usage over the trailing hour," recomputed as new data points arrive, is the moving-average pattern from Module F-7 applied at dashboard scale — maintaining a running sum/count rather than re-querying and re-averaging the full trailing hour on every tick.
Pagination with a cursor conceptually slides a window over an ordered result set — "give me the next page" moves the window forward without re-scanning everything before it.
Video/audio buffering: a player loads the next chunk once playback is partway through the current one — a window of "buffered content" that expands ahead of the playhead and contracts behind it as older chunks are discarded from memory.
Summary
A sliding window avoids recomputing overlapping work by maintaining a running result and adjusting it incrementally as the window moves, instead of recalculating from scratch for every position.
Fixed-size windows (max sum of any k consecutive elements) add the incoming element and subtract the outgoing one — O(1) per step, O(n) overall.
Variable-size windows expand on one side and contract on the other in response to a constraint being violated — both pointers only ever move forward, bounding total work to O(n) despite the nested-looking loop structure.
The expand/contract skeleton generalizes across "longest substring without repeating characters," "at most K distinct characters," and "smallest window containing a target set" — the constraint changes, the pointer discipline doesn't.
This pattern runs your production rate limiters, trailing-window metrics, and buffering logic — anywhere "the last N seconds/items" needs to update cheaply as new data arrives.
The next module, Intervals and Line Sweep, shifts from windows over a single sequence to reasoning about many overlapping ranges at once — the structure behind meeting-room scheduling and merging overlapping time periods.
Knowledge Check
In maxSumSliding, why does windowSum += nums[i] - nums[i - k] correctly update the window sum without needing to re-sum all k elements?
In longestUniqueSubstring, why is the overall time complexity O(n) despite the while loop being nested inside the for loop?
According to the module, what is the general three-step skeleton shared by variable-size sliding window problems like "longest substring without repeating characters" and "smallest window containing all target characters"?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
// O(n × k) — for every window, sum all k elements from scratchfunctionmaxSumBrute(nums:number[], k:number):number{let best =-Infinity;for(let i =0; i <= nums.length - k; i++){let sum =0;for(let j = i; j < i + k; j++) sum += nums[j];// recomputes the whole window every time best = Math.max(best, sum);}return best;}
// O(n) — one pass, constant work per stepfunctionmaxSumSliding(nums:number[], k:number):number{let windowSum =0;for(let i =0; i < k; i++) windowSum += nums[i];// sum the first window oncelet best = windowSum;for(let i = k; i < nums.length; i++){ windowSum += nums[i]- nums[i - k];// add the new element, drop the one that just exited best = Math.max(best, windowSum);}return best;}
functionlongestUniqueSubstring(s:string):number{const seen =newSet<string>();// Module F-4 — O(1) membership checkslet left =0;let best =0;for(let right =0; right < s.length; right++){// Constraint violated: shrink from the left until the duplicate is gonewhile(seen.has(s[right])){ seen.delete(s[left]); left++;} seen.add(s[right]); best = Math.max(best, right - left +1);}return best;}longestUniqueSubstring('abcabcbb');// 3 — "abc"longestUniqueSubstring('bbbbb');// 1 — "b"