🍳 IntuitiveFE
Login
← All concepts

Sliding Window

⏱️ ~2-minute bite · solve the sandbox to master

0%lesson
🧒

5-Year-Old Metaphor

— The physical, real-world picture. No jargon.

🔍 A magnifying glass gliding over a film strip — never re-reading a frame it already passed.

The naive approach (what most people write first)

You have a strip of 8 film frames: [2, 1, 5, 1, 3, 2, 4, 1]. Find the 3 brightest consecutive frames.

The brute force approach: place the glass at frame 0, sum frames 0+1+2. Move it to frame 1, sum frames 1+2+3 from scratch. Move it to frame 2, sum frames 2+3+4 from scratch. You re-read frames 1 and 2 on the second pass. You re-read frames 2 and 3 on the third. Every frame gets touched roughly k times. For 10,000 frames and k=100 that's 1,000,000 operations.

The sliding trick (the aha moment)

When you slide the glass one frame to the right, only two things change:

  • One new frame enters from the right → add it
  • One old frame falls off the left → subtract it
  • Everything in the middle is the same sum as before

That's one addition + one subtraction per slide. For the same 10,000 frames and k=100 that's 10,000 operations — 100× faster.

Visualised step-by-step

Array: [2, 1, 5, 1, 3, 2, 4, 1] k=3
— OPEN (build first window) —
window=[2, 1, 5] sum=8 best=8
— SLIDE (each step: +right, -left) —
drop 2, add 1 → [1, 5, 1] sum=7 best=8
drop 1, add 3 → [5, 1, 3] sum=9 best=9 ★
drop 5, add 2 → [1, 3, 2] sum=6 best=9
drop 1, add 4 → [3, 2, 4] sum=9 best=9
drop 3, add 1 → [2, 4, 1] sum=7 best=9
Answer: 9 (window at index 2: [5,1,3])

When to reach for this pattern

  • Problem mentions "contiguous subarray" or "substring"
  • There's a fixed size k or a constraint like "sum ≤ target"
  • You need to find max/min/count over a range that moves through the array
  • The array doesn't need to be sorted

⚠️ Pitfall: variable window with negatives + "sum ≤ target" — shrinking the window doesn't reliably decrease the sum. Use prefix sums + hashmap instead.

🎛️

Interactive Sandbox

— Move something, see it react instantly.
How to use: drag the k slider to pick a window size, then step or auto-play to watch the algorithm run frame-by-frame. The 🔍 magnifying glass is your window sliding across the array. The ★ marks the best subarray found so far.

k=3 means you look at 3 consecutive elements at a time.

array indices →
2
★[0]
1
★[1]
5
★[2]
1
[3]
3
[4]
2
[5]
4
[6]
1
[7]

2

window sum

2

best sum ★

1 / 8

step

[OPEN]Opening window — adding arr[0]=2, running sum=2
🎯

Challenge

Set the window size so the best window sum is maximized, then play to the end. (Hint: optimal k = 8.)

Try it
🎯

Why Should I Care?

— The exact interview question + the bug it kills.

Exact interview question (fixed window)

"Given an integer array and integer k, return the maximum sum of any contiguous subarray of size k."

ts
1function maxSum(arr: number[], k: number): number {
2 let sum = 0, best = -Infinity;
3 for (let r = 0; r < arr.length; r++) {
4 sum += arr[r]; // add entering element
5 if (r >= k - 1) {
6 best = Math.max(best, sum);
7 sum -= arr[r - k + 1]; // drop leaving element
8 }
9 }
10 return best;
11}
12// Time: O(n) · Space: O(1)

Harder variant (variable window) — very common at FAANG

"Find the length of the longest substring without repeating characters."

ts
1function lengthOfLongestSubstring(s: string): number {
2 const seen = new Map<string, number>(); // char → last index
3 let left = 0, best = 0;
4 for (let right = 0; right < s.length; right++) {
5 const c = s[right];
6 if (seen.has(c) && seen.get(c)! >= left) {
7 left = seen.get(c)! + 1; // shrink: jump past duplicate
8 }
9 seen.set(c, right);
10 best = Math.max(best, right - left + 1);
11 }
12 return best;
13}
14// Time: O(n) · Space: O(min(n, alphabet))

Complexity comparison

ApproachTimeSpace
Brute force (nested loops)O(n·k)O(1)
Sliding windowO(n)O(1) fixed / O(k) variable

Production bugs this pattern prevents

  • Rate limiter "requests in the last 60s" — naive implementation scans the full timestamp array on every request. With sliding window + circular buffer, each check is O(1). At 50k RPS, the difference is thread-blocking vs invisible.
  • Moving average chart — a dashboard that recomputes average over the last N data points from scratch on every new point melts the main thread when N is large. Sliding window makes each tick O(1): add new value, subtract oldest.
  • Streaming percentiles — approximating p99 latency over a sliding time window. Same pattern: add incoming, evict expired.
🔬

The Deep Dive

— Spec refs, engine internals, the minutiae.

Two flavors — know which the question wants

Fixed window

  • Width k is given upfront
  • Both pointers move in lockstep (right = left + k)
  • O(n) time, O(1) space
  • Works with negatives
  • Examples: max sum of size k, product of k consecutive

Variable window

  • Constraint drives the size (sum ≤ target, k distinct chars)
  • Expand right freely, shrink left when constraint breaks
  • O(n) amortized, O(k) space for a hashset/map
  • Breaks with negatives + "sum ≤ target"
  • Examples: longest substring, minimum window substring

The amortisation argument (what interviewers probe)

Variable window looks O(n²) because there's a while (shrink) inside a for (expand). The interviewer will ask: "wait, isn't this nested?"

The correct answer: each element is visited at most twice — once when right passes it (it enters the window), once when left passes it (it leaves). Since left only ever moves forward and can advance at most n times total across the entire outer loop, the sum of all inner iterations ≤ n. Total work = O(2n) = O(n).

This is the same argument as the two-pointer amortization. If you can articulate it clearly in an interview, it signals a strong algorithmic foundation.

When sliding window breaks down

  • Negatives + variable window + "sum ≤ target" — shrinking the window might not decrease the sum if negative elements are inside. The monotonicity assumption breaks. Switch to prefix sums + sorted structure or prefix sums + hashmap.
  • Non-contiguous constraints — if elements can be skipped (pick any k elements), window doesn't apply; use sorting + greedy or DP.
  • 2D arrays — for "max sum rectangle", you can collapse rows using prefix sums to reduce to a 1D sliding window problem. O(n²·m) → O(n²·m) but with a manageable constant.

Common implementation bugs

  • Off-by-one on window open: the window is "full" at index k-1, not k. Check with if (r >= k - 1) before recording best.
  • Not initialising best to -Infinity: initialising to 0 breaks for all-negative arrays (the correct answer may be a negative number).
  • Hashmap not evicting stale entries: in the "no-repeat characters" pattern, you must check seen.get(c) >= left before jumping — the map may contain a prior occurrence that's already outside the window.

Related patterns to know next

  • Two Pointers — sibling pattern; same left/right idea but for sorted arrays (no hashmap needed)
  • Prefix Sums — when range queries aren't contiguous or you need O(1) range sums after O(n) pre-processing
  • Monotonic Deque — sliding window maximum (not sum) in O(n) using a deque that maintains a descending max
  • Kadane's Algorithm — maximum subarray sum with no fixed size constraint (dynamic programming, not sliding window)
🎤

Interview Questions

— Real questions from real interviews — with answers.

Use sliding window when the problem involves a contiguous subarray/substring and a constraint you can maintain incrementally.

Fixed window slides one step at a time; variable window shrinks the left pointer until the constraint is satisfied.

Check that the stored index is still inside the current window before jumping left.

O(n + m) — each character is visited at most twice (once by right, once by left).

A monotonic deque of timestamps — evict entries older than the window, count the rest.

🎮

Memory Game

— Quick quiz — lock the concept in long-term memory.
1/4

When sliding a variable window, in what order should the right and left pointers move?