13

Sliding Window

Keep a running summary of a contiguous slice, and update it in O(1) as the slice moves.

intermediate~75 min4 simulations10 problems

▶ guided lesson⚡ 1-minute summary↻ 14 recall cards

before this: Two Pointers · Arrays & Strings · Big-O

01 · why it exists

Why this exists, and the weight it carries

since?

Fixed-size sliding window

Running totals over the last k values are as old as moving averages in statistics; as an array technique it is programming folklore, and we found no single inventor to credit.

its jobs today

  • Monitoring dashboards: "average response time over the last 5 minutes" and 7-day moving averages are fixed windows over a time series — add the newest reading, subtract the oldest.
  • Stream processing: Apache Flink and Kafka Streams ship tumbling and sliding windows as built-in aggregations.
  • Text and DNA search: a rolling hash (Rabin–Karp) slides a window of k characters across the text; genomics tools scan k-mers the same way.

the weight it carries

Illustrative: one reading per second for a day is 86,400 readings, and a dashboard shows the 5-minute (k = 300) average at every second. Re-adding every window: 86,400 × 300 = 25,920,000 additions (about 2.6 crore). Sliding: one add + one subtract per second = 172,800 operations — 150× less.

without it

Every rolling average or "last k" check would re-scan its whole window: O(n·k) work, which turns into crores of operations on a single day of per-second data.

when · why · how

when
The size is given: "every k consecutive", "subarray of length k", "indices at most k apart", "an anagram of p" (size |p|).
why
Neighbouring windows share k − 1 elements, so each slide costs O(1) instead of O(k): O(n) total instead of O(n·k), with O(1) extra space for a sum (O(σ) for a count table).
how
Build the first k, then for (int right = k; right < n; right++) sum += nums[right] - nums[right - k]; — use long when k × max value can pass 2·10⁹.

02 · plain english

The idea in 30 seconds

Many questions ask about the best contiguous subarray or substring. Checking every one is O(n²) or worse.

Instead, keep a window [left, right] and a small summary of it (a sum, a count table). When the window moves, update the summary: one element in, one element out.

right only moves forward and left only moves forward, so each element is added once and removed once: O(n).

picture this

Task Manager's CPU graph shows only the last 60 seconds. Every second, one new reading appears on the right and the oldest drops off the left — the whole minute is never redrawn. A sliding window updates its summary the same way: one in, one out.

03 · remember

What you must know

  • Fixed window (size k is given): build the first k, then each slide adds nums[right] and removes nums[right - k].
  • Variable window (find the longest / shortest valid slice): grow with right; while the window breaks the rule, shrink with left.
  • The window state is whatever lets you answer "is this window valid?" in O(1): a running sum, a zero count, an int[26] letter count, a HashMap.
  • Longest valid window → record the answer after the shrink loop. Shortest valid window → record it inside the shrink loop, before each shrink.
  • Shrinking is only safe when the rule is monotonic: if a window is invalid, every bigger window containing it is invalid too (for shortest problems, the mirror: if a window is valid, every bigger one is valid). Negative numbers usually break this for sums.
  • The nested while does not make it O(n²): left moves at most n times in total over the whole run (amortized O(1) per step).
  • Need the max or min of every window? Keep a monotonic deque of indices — the front is always the answer.
  • Sliding window is same-direction two pointers where you care about everything between the pointers, not just the two ends.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Fixed window — one in, one out

The window keeps its size. Each slide is two operations — add the new number, drop the oldest — not k.

loading simulation…
sim

Variable window — grow, then shrink

`right` grows the window until the sum is big enough; `left` shrinks it while it stays valid.

loading simulation…
sim

Window state in a count table

The buckets show what is inside the window. A red bucket means a duplicate — shrink until it is gone.

loading simulation…
sim

Monotonic deque — the max of every window

Values in the deque only decrease. Smaller, older values are popped because they can never win again.

loading simulation…

05 · cost

Time & space, explained

Sliding window vs the alternatives
TimeExtra spacewhy
Brute force: every subarray, recompute from scratchO(n²)–O(n³)O(1)n²/2 subarrays, and summing or checking each one costs up to O(n) more.
Fixed window of size kO(n)O(1)Build the first window in k steps, then n − k slides of O(1) each.
Variable window (grow + shrink)O(n)O(1)right moves n times and left moves at most n times in total — at most 2n steps. Amortized O(1) per step.
Window + count array int[26] / int[128]O(n)O(σ) = O(1)σ is the alphabet size. The array has a fixed size no matter how long the input is.
Window + HashMap countsO(n) averageO(distinct)HashMap updates are O(1) on average; the map holds one entry per distinct key in the window.
Window max/min with a monotonic dequeO(n)O(k)Each index is pushed once and popped at most once; the deque never holds more than k indices.
Cost of one window operation
Timewhy
Add nums[right] to a running sum / countO(1)One addition or one array increment.
Remove nums[left]O(1)One subtraction or decrement — no shifting, the array is never modified.
"Is this window an anagram?" via Arrays.equals(need, have)O(26) = O(1)Compares two fixed-size arrays. Fine, but a matches counter makes it truly one step.
Window maximum by rescanningO(k)Looks at every element in the window again — this is what makes the brute force O(n·k).
Window maximum from a monotonic dequeO(1)The answer is always nums[deque.peekFirst()].

06 · java

Raw vs Collections Framework

Template 1 — fixed-size window

javamax sum of k consecutive numbersjava.util.*
class FixedWindow {    /** Largest sum of any k consecutive numbers (1 ≤ k ≤ nums.length). */    static int maxSumOfK(int[] nums, int k) {        int sum = 0;        for (int i = 0; i < k; i++) sum += nums[i];   // build the first window        int best = sum;        for (int right = k; right < nums.length; right++) {            sum += nums[right] - nums[right - k];     // one in, one out            best = Math.max(best, sum);        }        return best;    }}
  • Two phases: build the first window (i < k), then slide (right from k to n − 1).
  • The element leaving is always nums[right - k] — no separate left variable needed.
  • If sums can exceed ~2·10⁹ (e.g. 10⁵ values of 10⁵), use long sum.

Template 2 — variable-size window

javalongest subarray with sum ≤ limitjava.util.*
class VariableWindow {    /** Longest subarray with sum ≤ limit (all numbers are non-negative). */    static int longestWithSumAtMost(int[] nums, int limit) {        int left = 0, sum = 0, best = 0;        for (int right = 0; right < nums.length; right++) {            sum += nums[right];                 // 1. grow: take nums[right]            while (sum > limit) {               // 2. shrink while the window breaks the rule                sum -= nums[left++];            }            best = Math.max(best, right - left + 1); // 3. window is valid: record it        }        return best;    }}
  • Grow → shrink while invalid → record. Memorise this order; most variable-window problems are exactly this loop.
  • Use while, not if, to shrink: one new element can require several removals.
  • The window [left, right] has length right - left + 1.

Window state: count array vs HashMap

javaint[26] countsjava.util.*
class CountArray {    /** How many length-p windows of s are anagrams of p? Lowercase letters only. */    static int countAnagramWindows(String s, String p) {        if (p.length() > s.length()) return 0;        int[] need = new int[26], have = new int[26];        for (char c : p.toCharArray()) need[c - 'a']++;        int found = 0;        for (int right = 0; right < s.length(); right++) {            have[s.charAt(right) - 'a']++;                                         // add the new char            if (right >= p.length()) have[s.charAt(right - p.length()) - 'a']--;   // drop the old one            if (right >= p.length() - 1 && Arrays.equals(need, have)) found++;     // 26 checks = O(1)        }        return found;    }}
  • Known small alphabet (lowercase letters, ASCII) → int[26] or int[128]: faster, no boxing, Arrays.equals works.
  • c - 'a' turns a lowercase letter into an index 0–25. For any ASCII char, index int[128] with the char itself.
  • Unknown or huge key space (Unicode, integers, words) → HashMap with merge(key, 1, Integer::sum).
  • When a count drops to 0, remove the key — otherwise map.equals and map.size() will lie.

Monotonic deque with ArrayDeque

javaArrayDeque of indicesjava.util.*
class Solution {    public int[] maxSlidingWindow(int[] nums, int k) {        Deque<Integer> dq = new ArrayDeque<>();   // indices; values decrease front -> back        int[] result = new int[nums.length - k + 1];        for (int right = 0; right < nums.length; right++) {            if (!dq.isEmpty() && dq.peekFirst() <= right - k) dq.pollFirst(); // fell out of the window            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[right]) dq.pollLast(); // can never be max again            dq.offerLast(right);            if (right >= k - 1) result[right - k + 1] = nums[dq.peekFirst()]; // front = max        }        return result;    }}
  • Store indices, not values: you need the index to know when an element has left the window.
  • ArrayDeque gives O(1) at both ends. Never use the legacy Stack class or a LinkedList here.
  • Pop from the back while the back's value ≤ the new value; the front is then always the window max.
Java API you will actually use
calldoescost
s.charAt(i)Read one character without copying the stringO(1)
count[c - 'a']++Count a lowercase letter in an int[26]O(1)
Arrays.equals(a, b)Compare two count arrays element by elementO(len)
map.merge(key, 1, Integer::sum)Increment a count, creating it at 1 if missingO(1) avg
map.getOrDefault(key, 0)Read a count without null checksO(1) avg
map.remove(key)Drop a key whose count reached 0O(1) avg
set.add(x)Adds x; returns false if x was already in the windowO(1) avg
deque.offerLast(x) / pollLast()Push / pop at the back of an ArrayDequeO(1) amortized
deque.peekFirst() / pollFirst()Read / remove the front (the window max)O(1)

Window state over lowercase letters

→ int[26]

Tiny, fast, no boxing; compare with Arrays.equals.

Window state over any characters

→ int[128] (ASCII) or HashMap<Character, Integer>

Array if the range is known and small, map otherwise.

Window state over integers / words

→ HashMap<K, Integer>

Key space is too big for an array.

"Is this value already in the last k?"

→ HashSet<Integer> of the last k values

add returns false on a repeat; remove the value that slides out.

Max or min of every window

→ ArrayDeque<Integer> of indices (monotonic)

O(1) amortized per step; a heap would be O(log n).

Just a sum or a count of something

→ One int / long variable

No structure needed at all.

07 · recognise

Spot the pattern

"Contiguous subarray" or "substring" + longest / shortest / maximum / minimum

Variable sliding window

"Of size k", "every k consecutive", "average of each window"

Fixed sliding window

"At most k" distinct / zeros / replacements

Variable window; shrink while the count exceeds k

"Contains all characters of", "anagram", "permutation of" inside a longer string

Window + count array (fixed size for permutations, variable for covering)

Equal values "at most k indices apart"

Fixed window of the last k values in a HashSet

"Concatenation of all words" (every word the same length)

Window over words instead of letters — one run per starting offset

"Maximum / minimum of every window"

Monotonic deque of indices

Subarray sum equals k with negative numbers

Not a window — use prefix sums + HashMap (chapter on hashing & prefix sums)

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

  • Using if instead of while to shrink — one new element may need several removals.
  • Recording the answer in the wrong place: longest → after the shrink loop; shortest → inside it.
  • Applying a sum window to arrays with negative numbers: removing an element can make the sum go up, so shrinking is no longer safe.
  • Off-by-one in window length: it is right - left + 1, not right - left.
  • Fixed window: forgetting that the first full window ends at right = k - 1, so results start there.
  • Storing values in the deque for window max — you then can't tell when the front has left the window.
  • Not removing zero-count keys from a HashMap, so map.size() still counts characters that left the window.

tricks

  • Say the template out loud: "expand right, shrink left while invalid, record". Then fill in what valid means.
  • Before coding, define the window state in one sentence: "zeros = number of 0s in the window."
  • Ask yourself: "If this window is invalid, is every bigger window invalid too?" If yes, sliding window works.
  • Dry-run on a tiny input (5–6 elements) and write left, right and the state after each step.
  • Edge cases: empty input, k = 1, k = n, every element valid, no valid window at all (return 0 or "").
  • "At most k" problems can also answer "exactly k": exactly(k) = atMost(k) − atMost(k − 1).

09 · why & how

Questions you might be too shy to ask

How do I decide between a fixed and a variable window?

If the problem gives you the window size ("subarrays of length k"), it is fixed. If it asks you to find the best length ("longest", "shortest", "minimum window"), it is variable.

Why is the window length right - left + 1 and not right - left?

Both ends are inside the window. Example: left = 2, right = 4 covers indices 2, 3, 4 — that is 3 elements, and 4 - 2 = 2 misses one. Quick check: when left == right the window holds one element, so the formula must give 1.

In the fixed window, why does the slide loop start at right = k, and why does nums[right - k] leave?

The first window is indices 0..k-1, built before the loop. So the first new element is at index k. The window after adding right must be right-k+1..right. The one index that just fell off is right - k. Dry-run with k = 3: when right = 3 enters, index 3 - 3 = 0 leaves. Simple hai.

There is a while loop inside a for loop. Why isn't it O(n²)?

Count the moves of left, not the loop nesting. left only moves forward and never passes right, so over the whole run it moves at most n times. Total work: n moves of right + at most n moves of left = O(n).

When I move left forward, how do I know I didn't skip the best window?

In a longest problem you shrink only when [left..right] is invalid. Any window that starts at the old left and ends at right or later contains that invalid window, so it is invalid too (the monotonic rule). So the old left can never start a better answer again — throwing it away loses nothing. This is exactly why the rule must be monotonic before you trust the window.

Can left ever go past right? Is that a bug?

It can, by one, and that is fine. In Minimum Size Subarray Sum with nums = [5], target = 4: the shrink loop records length 1, subtracts 5 and moves left to 1 while right is 0. That just means the window is empty (sum 0). The next right grows it again. You only record while the window is valid, so an empty window is never recorded.

When does sliding window not work?

When shrinking can't be justified. Example: "subarray sum equals k" with negative numbers. Dropping a negative number makes the sum bigger, so "sum too big → shrink" is wrong. Use prefix sums + a HashMap there.

Where exactly do I update the answer?

For the longest valid window, update after the shrink loop (the window is valid again). For the shortest valid window, update inside the shrink loop, before removing nums[left] (each iteration is a valid window).

Should I use int[26] or a HashMap for the counts?

If the problem says lowercase (or uppercase) English letters, use int[26] — it is faster and simpler. Use int[128] for general ASCII. Use a HashMap only when keys are unbounded (integers, words, Unicode).

The problem asks me to count subarrays, not find the longest. How does a window count them?

After the shrink loop, [left..right] is valid, and so is every shorter window that ends at right: [left+1..right], …, [right..right]. That is right - left + 1 windows, so add that to the count at every step. For "exactly k", count atMost(k) - atMost(k - 1): a window with exactly k distinct values is counted in the first run but not in the second.

In Longest Repeating Character Replacement, why is it OK that maxFreq never goes down?

The answer only grows when a window has a higher maxFreq than before. A stale (too big) maxFreq can only keep the window the same size, never let an invalid window become the new best. So we skip the expensive recount.

In Minimum Window Substring, why does need[c] go negative, and why does missing change only sometimes?

need[c] = how many more copies of c the window still needs. Negative means spare copies. Example: t = "ABC" and the window has two B's → need['B'] = -1, one spare. Dropping a spare B takes need['B'] back to 0 — still covered, so missing stays the same. missing counts the copies of t still not covered. It drops by one when an arriving c was still needed (need[c] was above 0), and rises by one when a leaving c takes need[c] from 0 up to 1.

Is sliding window the same as two pointers?

It is a kind of same-direction two pointers. The difference is focus: sliding window keeps a summary of everything between left and right; basic two pointers usually only looks at the two elements being pointed at.

I understand the solutions when I read them, but I freeze on a new problem. What now?

That is normal — reading and writing are different skills. Before any code, answer three questions on paper: what is the window state? When is the window invalid? Am I finding the longest or the shortest? Then write the template from memory and fill in only those three blanks. Practise in this order: 643 → 3 → 1004 → 209 → 76. Each one reuses the last one's loop.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run.

  1. #643
    Maximum Average Subarray I
    EasyMetaBloombergGoogleAmazonMicrosoft
  2. #3
    Longest Substring Without Repeating Charactersmust-do
    MediumWalmartInfosysAdobeNetflixByteDance / TikTok+1
  3. #424
    Longest Repeating Character Replacementmust-do
    MediumBloombergAmazonGoogleMicrosoftByteDance / TikTok+1
  4. #567
    Permutation in Stringmust-do
    MediumWalmartMicrosoftAmazonBloombergGoogle+1
  5. #438
    Find All Anagrams in a Stringmust-do
    MediumAmazonMicrosoftMetaGoogle
  6. #76
    Minimum Window Substringmust-do
    HardAdobeByteDance / TikTokMetaLinkedInAirbnb+1
  7. #209
    Minimum Size Subarray Summust-do
    MediumByteDance / TikTokBloombergMicrosoftAmazonMeta+1
  8. #1004
    Max Consecutive Ones IIImust-do
    MediumLinkedInMetaAmazonMicrosoftGoogle
  9. #219
    Contains Duplicate II
    EasyNetflixAirbnbAmazonGoogleMicrosoft
  10. #30
    Substring with Concatenation of All Words
    HardSamsungAmazonGoogleMicrosoft

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

  1. #239
    Sliding Window Maximum
    Hardin Queues

    A fixed window whose max can't be updated by add/subtract — a monotonic deque keeps it in O(1) amortized.

  2. #933
    Number of Recent Calls
    Easyin Queues

    A window over time instead of indices: keep only the pings from the last 3000 ms, dropping old ones from the front.

  3. #862
    Shortest Subarray with Sum at Least K
    Hardin Queues

    LC 209 with negative numbers: the plain window breaks, prefix sums + a monotonic deque fix it.

  4. #560
    Subarray Sum Equals K
    Mediumin Hashing

    Exact sums with negatives are not a window problem — prefix sums + a HashMap count them in O(n).

11 · revise

The whole chapter on one screen

9 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

  1. what it is

    A window [left, right] over a contiguous slice plus a tiny summary of it. Each move adds one element and removes one, so the whole scan is O(n).

  2. use it when

    "Contiguous subarray / substring" + longest, shortest, max or min; "of size k"; "at most k"; an anagram or permutation inside a longer string.

  3. template

    Fixed: build the first k, then sum += nums[r] - nums[r - k];. The element leaving is always nums[r - k].

  4. template

    Variable: for (r…) { add(r); while (invalid) remove(l++); best = max(best, r - l + 1); } — grow, shrink while invalid, record.

  5. cost

    O(n): right moves n times, left at most n times. Space: O(1) for a sum, O(σ) for int[26] / int[128], O(k) for a deque.

  6. trap

    Negative numbers break sum windows: removing one can raise the sum. Use prefix sums + a HashMap instead.

  7. trap

    Longest → record after the shrink loop. Shortest → record inside it, before removing nums[left].

  8. trap

    Shrink with while, not if: one new element can force several removals.

  9. pro tip

    "Exactly k" = atMost(k) - atMost(k - 1). Max or min of every window → a monotonic ArrayDeque of indices.

12 · recall

Flip, remember, repeat

card 1 / 14
recall

There's a while inside a for. Why is the variable window still O(n)?

tap or Space to flip ↻

Question 1: There's a while inside a for. Why is the variable window still O(n)?

13 · check yourself

Quick quiz

  1. Fixed window, k = 3, nums = [2, 1, 5, 1, 3]. The first window sum is 8. What is the sum after one slide?

  2. Why is the variable window O(n) even though it has a while loop inside a for loop?

  3. "Count subarrays with sum exactly k" on an array with negative numbers. Best tool?

  4. Window-max deque holds values [9, 4, 2] (front → back). The new value is 5. What does the deque hold after the push?

  5. LC 424, k = 1. The window is "AABAB". Is it valid?

  6. You want the **shortest** valid window. Where do you update the answer?

  7. Window state over lowercase letters only. Which is the best choice?

  8. LC 219 with k = 2, nums = [1, 2, 3, 1]. Just before index 3 is checked, what does the HashSet window hold — and what is returned?

  9. LC 30 with words of length 3. How many separate word-by-word windows does the optimal solution run?

0/0 correct · 9 left

14 · learn more

A second teacher, if you want one