sum=0
A window defined by two indices — left and right — slides over a sequence. The right edge grows to pull elements in; the left edge shrinks to push elements out. Every element enters once and leaves once, collapsing an O(n²) brute-force into an amortized O(n) linear scan with O(1)–O(k) space.
Stop re-summing every subarray from scratch. Keep one window and a running tally: slide the right edge to grow, and only when the window breaks its rule do you slide the left edge to shrink. Each index enters once and leaves once, so an O(n²) re-scan collapses into a single O(n) sweep.
Picture a frame laid over a contiguous run of the array. Brute force lifts the frame up and lays it down at every possible (left, right) pair, re-adding the same elements again and again. The sliding window never lifts the frame — it just slides one edge at a time and updates a small running tally (a sum, a count, a frequency map) as elements cross the edges.
Adding an element on the right and dropping one on the left are each O(1). So the window's state is always up to date without recomputing it. The whole technique is: two cursors that only move right, plus a tally that you patch incrementally instead of rebuilding.
Here is the wasted work brute force does — every subarray re-added from scratch, so each element is touched O(n) times:
Brute force: longest/best subarray → try EVERY (i, j) pair
a = [ 2 1 5 1 3 2 ]
[2] sum=2
[2 1] sum=3 ◄ re-add the 2
[2 1 5] sum=8 ◄ re-add the 2 and 1
[2 1 5 1] sum=9 ◄ re-add the 2, 1, 5 ...
[1] sum=1
[1 5] sum=6 ◄ re-add the 1
...
~n²/2 sums, each rescanned anew.
Each cell is touched O(n) times. The waste IS the re-summing.Now keep a single window. The right edge grows greedily; the instant the rule breaks (here: a repeated character), the left edge catches up just enough to restore it. Both cursors only ever move right:
Longest substring without repeating chars: s = a b c a b c b b
idx 0 1 2 3 4 5 6 7
step window action len
───── ───────────── ────────────────────────────── ────
r=0 [a] grow right 1
r=1 [a b] grow right 2
r=2 [a b c] grow right 3 ◄ best
r=3 [a b c a]? 'a' repeats → shrink left ──┐
[b c a] left caught up, valid again ┘ 3
r=4 [b c a b]? 'b' repeats → shrink left
[c a b] valid 3
r=5 [c a b c]? 'c' repeats → shrink ... [a b c] 3
left ──► right ──► both cursors only ever move RIGHT.
Each of the 8 indices enters once, exits once → ≤16 moves → O(n).For a fixed width k, the frame slides in lock-step — add the incoming element, subtract the outgoing one — keeping the sum in O(1) per step:
Max sum of a window of size k = 3: a = [ 2 1 5 1 3 2 ]
frame [2 1 5] sum = 8
└──────┐ slide →
frame [1 5 1] sum = 8 - 2 + 1 = 7
└──────┐ slide →
frame [5 1 3] sum = 7 - 1 + 3 = 9 ◄ best
└──────┐ slide →
frame [1 3 2] sum = 9 - 5 + 2 = 6
Never re-add the whole frame: +incoming(right) -outgoing(right-k).
One add and one subtract per slide → O(1) per step, O(n) total.When a problem might be a window, climb these rungs in order. The code falls out at the bottom:
k”), it is a fixed frame: slide in lock-step. Otherwise it is variable: grow right, shrink left.(windowLen − maxFreq) ≤ k, “sum ≥ target”. Write it as one boolean.Map plus a formed counter? A monotonic deque? The tally must update in O(1) as each edge moves.Before coding, say the window's rule as one plain sentence: “the window is valid as long as ___; the moment that breaks, I shrink from the left until it holds again.” If you can state it, the shrink condition is just its negation.
windowLen − maxFreq ≤ k (the chars to replace fit the budget); shrink when it exceeds k.”kwide; drop the left element the moment it grows past k.”Strip away the specific rule and every sliding-window solution is one of two shapes. Read them as sentences, not code. Variable — grow right, shrink the left while invalid, record when valid:
left = 0
for right in 0 .. n-1: # grow: right ALWAYS advances
add a[right] to the tally # update window state in O(1)
while window is INVALID: # the invariant says "shrink now"
remove a[left] from tally
left += 1 # left only ever moves right
# window is valid here
best = max(best, right - left + 1)Fixed — the frame is always k wide, so the moment it grows past k you drop one from the left in lock-step:
for right in 0 .. n-1:
add a[right] to the tally # incoming element
if right >= k: # frame is too wide
remove a[right - k] from tally # outgoing element
if right >= k - 1: # first full frame onward
record answer from the tallyThe only things that change between problems are the tally you keep, the invalid condition, and whenyou record. The two-cursor shape never changes — which is exactly why windows become reflexive once you've internalized them. Critically, the inner shrink uses while, not if: one step may not restore validity.
A window only works because shrinking from the left is a safe, monotonic move: once a window is too big or invalid, no smaller window starting further left could be better, so left never needs to back up. Break that and the technique collapses.
A sliding window is a contiguous subarray or substring defined by two index cursors, left and right, that always satisfy left ≤ right. You advance right on every iteration to grow the window, then conditionally advance leftto restore a broken invariant. The window "slides" rightward across the sequence.
k wide. Advance both edges in lock-step: add the new right element, drop the old left element, record the answer.right advances on every outer iteration (one pass over the array). left advances only when the invariant is broken. Use a while inner loop — not if — so you keep shrinking until the window is valid again, not just once.For a longest-valid-window problem, record the answer after shrinking (the window is guaranteed valid at that point). For a shortest-valid-window problem (like Minimum Window Substring), record the answer inside the shrink loop — every valid window is a candidate.
Even though there is an inner while loop, the total number of times left advances across the entire outer loop is at most n. The amortized cost per element is O(1), giving O(n) overall — plus O(k) for any auxiliary structure (hash map, deque) bounded by the window contents.
Two common augmentations to the plain two-pointer window:
Map<string, number> alongside the window. Increment on entry, decrement on exit. A formed counter tracks how many distinct requirements are currently satisfied, so you never re-scan the map to check validity.7. Grow greedy, shrink to stay legal. Right pointer expands the window; once it's legal, the left pointer tightens it.Sliding window is the answer when you need an optimal contiguous subarray or substring, and the validity condition changes monotonically as the window grows — so that you never need to revisit a smaller window after expanding.
| "longest / shortest contiguous subarray or substring" with a constraint | variable-size window; shrink while constraint is violated |
| "max / min sum (or average) of exactly k elements" | fixed-size window of width k; slide in lock-step |
| "at most K distinct characters / values" | variable window + frequency map; shrink when distinct count exceeds K |
| "contains all characters of T" / "minimum window containing T" | need/have frequency map + shrink-while-formed-equals-required |
| "permutation of s1 exists in s2" / "anagram in a string" | fixed window of size len(s1); compare frequency arrays each step |
| "maximum of every window of size k" | monotonic decreasing deque of indices; front is the window max |
| "longest subarray with at most k replacements / zeros" | variable window; invariant is (windowLen - maxFreq) ≤ k |
prefixSum[j] − prefixSum[i] = k) for O(n) time instead.When → You want the longest contiguous subarray / substring satisfying some constraint. Grow right unconditionally; shrink left with a while loop until the window is valid again, then record.
function longestWindow(s: string, isValid: (window: string, freq: Map<string, number>) => boolean): number {
const freq = new Map<string, number>();
let left = 0;
let best = 0;
for (let right = 0; right < s.length; right++) {
// 1. Expand: admit s[right] into the window
freq.set(s[right], (freq.get(s[right]) ?? 0) + 1);
// 2. Shrink WHILE the window violates the invariant
while (!isValid(s, freq)) {
const c = s[left];
freq.set(c, freq.get(c)! - 1);
if (freq.get(c) === 0) freq.delete(c);
left++;
}
// 3. Record the answer — window is always valid here
best = Math.max(best, right - left + 1);
}
return best;
}while, not if, to shrink → a single shrink step may not be enough to restore validity. The inner while is still amortized O(1) per element overall.When → The window is always exactly k elements wide. Add the incoming right element and drop the outgoing left element (nums[right - k]) every iteration. Start recording once right ≥ k − 1.
function fixedWindowMax(nums: number[], k: number): number[] {
const result: number[] = [];
let windowSum = 0;
for (let right = 0; right < nums.length; right++) {
windowSum += nums[right]; // grow: add incoming element
if (right >= k) {
windowSum -= nums[right - k]; // shrink: drop the element leaving the left
}
if (right >= k - 1) { // window is full for the first time
result.push(windowSum); // (swap for max / min as needed)
}
}
return result;
}right − k (not right − k + 1), and the window length is always right − left + 1.When → You want the shortest window that satisfies a frequency requirement — classic Minimum Window Substring style. Track a need map from the target, a have map for the window, and a formed counter. Record the answer inside the shrink loop.
function minWindowSubstring(s: string, t: string): string {
// Build the "need" map from t
const need = new Map<string, number>();
for (const c of t) need.set(c, (need.get(c) ?? 0) + 1);
const have = new Map<string, number>();
let formed = 0; // how many chars satisfy their required count
const required = need.size;
let left = 0;
let best = '';
for (let right = 0; right < s.length; right++) {
const c = s[right];
have.set(c, (have.get(c) ?? 0) + 1);
// Did we just satisfy this character's required count?
if (need.has(c) && have.get(c) === need.get(c)) formed++;
// Shrink while the window satisfies all requirements
while (formed === required) {
const window = s.slice(left, right + 1);
if (best === '' || window.length < best.length) best = window;
const lc = s[left];
have.set(lc, have.get(lc)! - 1);
if (need.has(lc) && have.get(lc)! < need.get(lc)!) formed--;
left++;
}
}
return best;
}formed counter is the key optimisation →it avoids re-scanning the entire map on every step. Increment it only when a character's have count exactly reaches its need count (not every time you see that character).When → You need the maximum (or minimum) of the current window in O(1) per step. A monotonic decreasing deque of indices keeps the front as the window maximum; stale front indices and dominated back indices are evicted before each push.
function slidingWindowMaximum(nums: number[], k: number): number[] {
const result: number[] = [];
const dq: number[] = []; // stores INDICES, front = largest element's index
for (let right = 0; right < nums.length; right++) {
// Remove indices that have left the window
while (dq.length && dq[0] < right - k + 1) dq.shift();
// Maintain decreasing order: pop smaller values off the back
while (dq.length && nums[dq[dq.length - 1]] < nums[right]) dq.pop();
dq.push(right);
if (right >= k - 1) { // window is full; front is the max index
result.push(nums[dq[0]]);
}
}
return result;
}dq[0] < right − k + 1). Comparing values alone can't tell you that.The single most common sliding-window bug. After expanding right, one shrink step may not be enough — the invariant can still be violated. Always use a while inner loop so the window is fully restored before you record the answer or move on.
For a longest window, record after shrinking — the window is guaranteed valid at the bottom of the outer loop. For a shortest window (Minimum Window Substring style), record inside the shrink loop — every valid state before another shrink is a candidate. Mixing these up gives wrong answers on edge cases.
When you advance left, you must decrement the outgoing character in your frequency map — and delete the key if the count reaches zero, or your formed / distinct-count tracking will overcount. In fixed-size windows, subtract nums[right - k] from the running sum before the next addition.
A window spanning indices left through right (inclusive) has length right − left + 1, not right − left. In fixed-size windows, the first full window is complete at right === k − 1, and the element leaving the window is at right − k (one position before the new left). Double-check both of these on a small example before submitting.
Set (or last-seen index map). Shrink left until the duplicate is evicted; window length at each step is the candidate best. The index-map variant skips left directly to lastSeen[c] + 1 instead of stepping one-by-one.#424Longest Repeating Character ReplacementVariable window; the invariant is (windowLen − maxFreq) ≤ k. Track the frequency of each letter and the running maximum frequency. When the invariant breaks, shrink left by one and update the count — you only need to shrink by one because you're looking for a longer window than any seen before.#76Minimum Window SubstringThe canonical need/have template. Build a need map from t, maintain a have map and a formed counter. Shrink while formed === need.size, recording each valid window before shrinking further.#239Sliding Window MaximumFixed window of size k + monotonic decreasing deque of indices. Evict expired front indices, pop dominated back values, push the new index, then emit nums[dq[0]] once the first full window is formed.#567Permutation in StringFixed window of size s1.length. Slide across s2, maintaining a frequency delta array (or two frequency maps). The window contains a permutation of s1 exactly when all 26 character counts match.#438Find All Anagrams in a StringSlide a fixed window of length |p| across s, maintaining a 26-letter frequency match; record the start index every time the window's letter counts equal p's. O(n) time.#209Minimum Size Subarray SumFind the shortest contiguous subarray whose sum is at least target by growing a window to the right and shrinking from the left while it stays valid — an O(n) sweep that works because all values are positive.#1004Max Consecutive Ones IIIFind the longest run of 1s you can make by flipping at most k zeros: a variable window that holds at most k zeros, shrinking from the left whenever a (k+1)th zero enters. O(n) time, O(1) space.