Week 3: Sliding Window

Pattern family: Sliding Window · Time budget: 13 hours · Prerequisites: Weeks 1 and 2 done, with hash maps and the Counter (Week 1) and the two-pointer “move one index, then the other” rhythm (Week 2) fresh. · Cold-revisit obligation: Contains Duplicate, 3Sum.

Overview

Sliding window is what you reach for when the question is about a contiguous run, a subarray or a substring, and you want the longest, the shortest, or the best one that satisfies some condition. The brute force is to look at every possible run, which is O(n^2) starts times the work to check each. The window collapses that: keep two indices, a left and a right, that bound the current run, and as right advances you update a small amount of state instead of re-scanning the whole run. Each end moves forward only, never backward, so the whole sweep is one linear pass.

The pattern comes in two shapes, and telling them apart is half the week. A fixed window has a known size k and slides as one rigid block; you add the element entering on the right and drop the one leaving on the left. A variable window grows and shrinks: you expand right to take in more, and you shrink left whenever the window violates its constraint. The variable case is the one that trips people, because the skill is knowing the exact condition that triggers the shrink. Most of this week is training the move that fires before any code: catch the words “longest”, “shortest”, or “best contiguous”, and reach for two indices and a piece of running state.

flowchart TD
    Q["Read the problem"] --> A{"Is the answer a contiguous<br/>subarray or substring,<br/>under some constraint?"}
    A -->|no| G["Probably hashing, two pointers<br/>on a sorted array, or a different<br/>pattern. Keep reading the cues."]
    A -->|yes| B{"Is the window size fixed (given k),<br/>or does it grow and shrink<br/>with the constraint?"}
    B -->|"fixed size k"| F["Fixed window: add the entering<br/>element, drop the leaving one,<br/>read the answer each step."]
    B -->|"variable"| V["Variable window: expand right to<br/>include more, shrink left while the<br/>window is invalid, track the best."]

Notice: the decision happens before you code, and it has two beats. First, is the answer a contiguous run at all? Second, is the window a fixed block or a growing-and-shrinking one? Naming the pattern out loud (principle 1) is what makes this diagram fire under pressure.

Warm-Up: Retrieve Before You Begin

Answer from memory, no peeking. This pulls forward the prior-week tools that sliding window leans on hardest.

From Week 1: what does collections.Counter(t) give you, and what does counts["x"] return when "x" was never in the input?
From Week 2: in a two-pointer sweep you advance one index, then sometimes the other. What is the property that makes that a single O(n) pass rather than a nested loop?
From the refresher: a list is O(n) to pop from the front. Which container gives you O(1) removal from the front, and what are its two front operations?

Check your recall

1. `Counter(t)` returns a `dict` subclass mapping each character of `t` to how many times it appears. A missing key returns `0` rather than raising `KeyError`, which is exactly what lets you write `counts[ch] -= 1` on a character you have not seen without a guard clause. 2. Each index only ever moves forward, never backward. Across the whole run `left` advances at most n times total and `right` advances at most n times total, so the combined work is O(n), even though both are inside the same loop. That "each pointer is monotonic" property is the difference between a window and a nested scan. 3. `collections.deque` gives O(1) removal from the front. The front operations are `popleft()` (remove and return the leftmost element) and `appendleft(x)` (add on the left); you will mostly use `popleft()` plus `append(x)` on the right for the window-maximum deque.

Learning objectives

By the end of this week you can:

Recognize the contiguous-subarray-or-substring cue and reach for a sliding window without being told.
Distinguish a fixed window from a variable window, and state which one a problem needs and why.
Construct the expand-right / shrink-left loop, naming the exact condition that triggers the shrink.
Choose the right window state for the problem: a running sum, a set, a Counter, or a monotonic deque.
Analyze the time and space complexity of your solution and name what dominates at scale.
Defend every line of each solution you commit, from memory, with no AI open, including why each index moves forward only.

Recognition cue

“Find the longest, shortest, or best contiguous subarray or substring satisfying condition X” almost always means a sliding window. The surface phrases are “longest substring with …”, “smallest subarray such that …”, “maximum sum of any window of size k”, and anything that says “contiguous” out loud. The deeper tell is that a brute force would re-examine overlapping runs again and again; the moment you notice that two adjacent candidate runs share almost all their elements, you are looking at a window that should slide instead of restart.

Core concepts to internalize this week

Fixed window vs variable window. A fixed window has a size handed to you (k); it slides as a rigid block, one in on the right and one out on the left per step. A variable window has no fixed size; it expands to take more in and shrinks when it breaks its constraint. Deciding which one you are in is the first move, because it determines the entire loop shape.
The expand-right / shrink-left rhythm. The variable-window template is: for each right, add s[right] to the window state; then while the window is invalid, remove s[left] and advance left; then record the answer (longest valid window, or shortest, depending on the question). The whole craft is naming the invalid condition precisely.
Window state is the part you choose. The window is summarized by a small piece of state you update in O(1) as the ends move: a running sum for “subarray sum”, a set for “all distinct”, a Counter for “have vs need” character counts, a monotonic deque for “max in the window”. Picking the state is most of the problem. One caveat on the running sum: a sliding window over “subarray sum” is correct only when every value is non-negative, so the sum grows monotonically as the window widens and shrinking on “sum too big” is safe. If the array can contain negatives, the sum is no longer monotonic and the window silently breaks; the right tool there is a prefix-sum plus a hash map of seen prefix sums (see Week 1), not a sliding window.
The have-vs-need Counter. When the constraint is “the window must contain at least these characters” (Minimum Window Substring), you hold a Counter of what you need and track how many requirements are still unmet. Expand until nothing is unmet, then shrink to find the tightest such window. This is the canonical machinery of the week.
The monotonic deque for window maximum. To report the maximum of every window of size k in O(n) total, keep a deque of indices whose values are in decreasing order. Before pushing a new index, pop smaller values off the back (they can never be the max while the new one is present); the front is always the current window’s maximum; drop the front when it slides out of range.
Best Time to Buy and Sell as a degenerate window. “Buy on one day, sell on a later day, maximize profit” is a window where left marks the cheapest day seen so far and right is today; you never look back past the cheapest buy. It is the smallest possible variable window, and seeing it as one is the lesson.

Common misconception. “Sliding window means a fixed-size block of size k that I slide across the array.” Reality. That is only the fixed-window case. The harder and more common interview case is the variable window, which grows and shrinks based on a constraint and has no fixed size at all (Longest Substring Without Repeating Characters, Minimum Window Substring). Before you write any code, decide out loud which of the two you are in; using the fixed-window mental model on a variable-window problem is the single most common way these solutions come out wrong.

Common misconception. “Shrinking the window from the left could miss a better answer further left, so a window cannot be correct here.” Reality. Because both indices only move forward, once left has advanced past a position, no valid window starting at that position can be better than one you already recorded (you recorded the best window ending at every right along the way). The forward-only movement is exactly what makes the single pass complete, not lossy. Convince yourself of this on Longest Substring Without Repeating; it is the insight an interviewer probes.

Python idioms this week

You are not yet expected to be fluent, so here is the toolbox this week uses. If any is unfamiliar, open the Python refresher before Monday.

collections.deque for the monotonic-deque window max: append (push right), pop (pop right), popleft (pop the front), and appendleft if you ever need it. The deque holds indices, not values, so you can tell when the front slides out of range.
collections.Counter as window state for the have-vs-need machinery; remember a missing key reads as 0, so counts[ch] -= 1 is safe without a guard.
A plain dict or set as window state when you only need “have I seen this character inside the current window”.
Dict and set membership checks (ch in window) in O(1) average.
max(...) and min(...) over a running value, to track the best window length or the cheapest buy seen so far.
enumerate(s) to walk a string with the index (your right) and the character together.

These are tools you are allowed to know cold in an interview. The pattern (fixed vs variable, what the window state is, when to shrink) is the part you build yourself.

Pattern Card requirement

Before you solve the canonical problem, write your Pattern Card at .tutor/pattern-cards/sliding-window.md. It must contain:

The recognition cue, in your own words.
The algorithmic skeleton in pseudocode (the expand-right / shrink-left template, and a note on the fixed-window variant).
Time and space complexity, general form (why the two-index sweep is O(n), and what the window state costs in space).
Three edge cases (empty input, a window larger than the input, and a single element are good starts).
One war story (a bug you actually hit this week); fill this in at the end of the week.

The first four sections must be present before you start the canonical deep-dive. The tutor will probe the card; it will not write any of it for you.

Canonical deep-dive

Problem: Minimum Window Substring (https://leetcode.com/problems/minimum-window-substring/)

Minimum Window Substring is this course’s home for the have-vs-need Counter machinery, the most reusable idea in the sliding-window family. The full guided walk-through, with the window state, the expand-then-shrink rhythm, and the exact complexity, is in canonical/minimum-window-substring.md. Work it there. You will implement it yourself, in your own work repo, and write a short debrief. The walk-through is deliberately not an answer key: it shows you how to think, and stops short of code you could paste.

Practice set

Four problems, in this order. Each has its own folder under practice/ with the problem link, a complexity target for you to fill in, and the debrief template. Do not skip ahead.

Best Time to Buy and Sell Stock (practice/best-time-to-buy-and-sell-stock/). The smallest possible variable window: left tracks the cheapest buy, right is today. This is the problem that shows you “track the best seen so far” is a window.
Longest Substring Without Repeating Characters (practice/longest-substring-without-repeating-characters/). The archetypal variable window: expand right, and shrink left whenever a repeat enters, keeping the window all-distinct.
Longest Repeating Character Replacement (practice/longest-repeating-character-replacement/). A variable window where the constraint is “window length minus the count of its most frequent character is at most k”. Naming that condition is the whole problem.
Sliding Window Maximum (practice/sliding-window-maximum/). A fixed window of size k where the answer for each window is its maximum; the monotonic deque is what makes it O(n) instead of O(n*k).

Each problem follows the five-beat rhythm.

The five-beat rhythm (every problem)

Pattern Card is written (you did this Monday).
Name the pattern aloud and write your approach as a plain-English comment before any code.
Struggle floor: 25 minutes unaided.
Hint ladder if needed: six rungs, one per ask.
Debrief: the five questions, in your commit message, before the next problem.

Reflect

Ten minutes in your notebook, in writing:

Explain it back: describe the difference between a fixed and a variable window to a peer who has only done arrays and two pointers so far, in three sentences.
Connect: Week 2 called two pointers a special case of sliding window. In your own words, what does a variable window add that a two-pointer sweep on a sorted array does not have?
Monitor: which window state (running sum, set, Counter, deque) is still the one you are unsure when to reach for? Write the one sentence that would clear it up.

Knowledge Check

Answer from memory first. Items marked ⟲ are spaced callbacks to earlier material.

What input shape or phrase in a problem statement should make you reach for a sliding window?
State the expand-right / shrink-left template for a variable window in your own words, and name the one decision that makes or breaks it.
In Sliding Window Maximum, why does the deque hold indices rather than values, and why is the whole sweep O(n) even though there is an inner while loop?
⟲ From Week 1: in Minimum Window Substring you hold a Counter of needed characters. Why is it safe to write need[ch] -= 1 for a character that is not in t, and what does a negative count then mean?
⟲ From Week 2: two pointers on a sorted array and a sliding window both move indices forward only. What does the window do that the sorted-array two-pointer sweep does not, and what state does that require?

Answer key

1. "Longest", "shortest", "smallest", or "best" applied to a *contiguous* subarray or substring under some constraint, or any "window of size k" phrasing. The deeper tell is that a brute force would re-scan heavily overlapping runs. 2. For each `right`, add `s[right]` to the window state; `while` the window violates its constraint, remove `s[left]` and advance `left`; then record the answer (longest or shortest valid window). The make-or-break decision is naming the exact "violates its constraint" condition that triggers the shrink. 3. The deque holds indices so you can check whether the front has slid out of the current window (`front <= right - k`) and drop it; values alone would not tell you position. The sweep is O(n) because every index is pushed onto the deque once and popped at most once, so the total pop work across all iterations is bounded by n, not multiplied by the window size. 4. A `Counter` (and any `dict` accessed through it) returns `0` for a missing key rather than raising, so `need[ch] -= 1` is well defined for any character. A negative count means the window holds more copies of `ch` than `t` requires, which is the surplus you are allowed to shrink away from the left. 5. The window grows *and* shrinks based on a constraint, where a sorted-array two-pointer sweep just walks both ends inward once. To support shrinking correctly, the window must carry a small piece of state (a sum, a set, a Counter, or a deque) that it can update in O(1) as either end moves.

Cold revisit

This Friday, before any new work, re-solve two prior problems cold: no notes, no prior code open, no AI, the standard 25-minute floor on each.

Contains Duplicate (Week 1, Arrays and Hashing). https://leetcode.com/problems/contains-duplicate/ A blind re-solve. Do not look at which pattern it is until you have named it yourself; recognizing it cold is the point.
3Sum (Week 2, Two Pointers). https://leetcode.com/problems/3sum/ A blind re-solve, same rules.

Neither is a sliding-window problem, and that is deliberate: one is hashing and one is two pointers, so the cold revisit trains recognition across the whole course, not just this week’s pattern. Debrief each at the end and log the outcome in .tutor/revisit-log.md.

How to know you are done with this week

Pattern Card complete at .tutor/pattern-cards/sliding-window.md, including the war-story field.
Canonical deep-dive done: Minimum Window Substring implemented yourself, with your short debrief (in your work repo).
Four practice problems solved, each with a five-question debrief in its commit message.
.tutor/revisit-log.md updated by the tutor with this week’s problems and the two cold revisits, with dates.
.tutor/progress.md updated to “Week 3 complete; ready for Week 4.”

If any of the above is missing, the week is not done. The tutor will not advance you to Week 4 until all five are present.

Resources

Free, no account required:

[Article] The sliding window technique, the idea (arrays and strings): https://www.geeksforgeeks.org/window-sliding-technique/
[Docs] Python collections (Counter, deque): https://docs.python.org/3/library/collections.html
[Docs] Python collections.deque: https://docs.python.org/3/library/collections.html#collections.deque