The sliding window
A huge family of real questions asks about every consecutive range of a sequence: the busiest 3-day stretch in a metrics dashboard, the most requests in any 60-second span of a server log, the longest run of distinct items. These power monitoring alerts and rate limiters, and they are one of the most common interview question shapes.
The naive plan recomputes each range from scratch: for each of ~n starting positions, re-add k items. That is O(n × k) — and when the range can be the whole sequence, O(n²).
The sliding window pattern removes the waste with one observation: consecutive ranges overlap in all but two items. Moving the window one step right means exactly one item enters and one item leaves. So instead of recomputing, update: add the entering item, subtract the leaving one. Each item enters the window once and leaves once over the whole pass, so the total work is O(n) no matter how big k is.
O(1) indexing (lesson 2-1) is what makes the update cheap: temps[i] and temps[i - k] are both single address computations.
Code exercise · python
Run this. Both versions find the best 3-day total, but the naive one re-adds every window from scratch (k × windows additions) while the sliding version does two operations per step. At k = 3 the gap is small; at k = 10,000 the naive count would be ~10,000× worse and the window count would not change.
Quiz
Why is the sliding-window pass O(n) even though every window has k items in it?
Windows that grow and shrink
Some questions fix no size k. Take the classic: longest substring with no repeated character ("abcabcbb" → "abc", length 3). Here the window is variable: the right edge grows one character at a time, and whenever the new character is already inside the window, the left edge shrinks until the duplicate is gone.
Two indexes, left and right, mark the window — the two-pointer idea from lesson 3-2, except both pointers now move in the same direction. Membership ("is this character already in the window?") must be O(1) or the shrink check becomes a scan, so the window's contents live in a set — the same jump-straight-to-it lookup as the dict in lesson 1-1 (unit 6 shows the machinery).
The cost stays O(n) by the same per-item argument: right moves forward n times, and left only ever moves forward, so it too moves at most n times total. The inner while loop looks nested but cannot run more than n times across the entire pass.
Code exercise · python
Your turn: implement `longest_unique(s)`. Grow the window with `right`. While `s[right]` is already in the `seen` set, remove `s[left]` from the set and advance `left`. Then add `s[right]` and update `best` with the current window length, `right - left + 1`.
Problem
A window of size k slides across n items using the add-one/drop-one update. Across the WHOLE pass, how many times is each individual item added into the window total: once, k times, or n times?