Sliding Window Problems

Six classic interview problems — Best Time to Buy and Sell Stock, Longest Substring Without Repeating Characters, Longest Repeating Character Replacement, Permutation in String, Minimum Window Substring and Sliding Window Maximum — solved from zero with one idea: look at a stretch of neighbouring items, and when you move on, only update what changed at its two edges. For each problem you will see the slow obvious idea, why each move of the window is safe, the pseudocode, the Dart code, and an animation you can feed your own input. By the end you will know when a window applies, whether it should have a fixed or a changing size, what it must remember, and why a loop inside a loop can still be O(n).

What a sliding window is and why it is fast

Some words first:

• A window is a contiguous range of a list or a string: all the items from position left to position right, with nothing skipped. We write it [left, right]. Its length is right − left + 1. "Contiguous" is the key word: a window of [4, 9, 1, 7] can be [9, 1] but never [4, 1].
• left and right are just whole numbers that hold positions (indexes, counted from 0). They are the two pointers from Step 13.2 · Remove Duplicates, but here both move in the same direction, left to right, and the items between them form the window.
• Grow means "move right one step": a new item enters the window. Shrink means "move left one step": the oldest item leaves.
• O(n) ("order n") means the work grows in step with the input size n; O(n²) means twice the input gives four times the work. See C03 · Growth of Functions.

Fixed-size windows

Some problems fix the length: "the sum of every 3 days in a row", "is any 4-letter piece of this text a rearrangement of abcd?". The window always holds exactly k items. Each step, one item enters on the right and one leaves on the left, and we update a running answer with just those two items. The brute force re-adds all k items for every window, O(n·k); the window does it in O(n). Watch the running sum:

Variable-size windows: grow right, shrink left

Most problems ask for the longest or shortest window that obeys a rule ("sum at most 6", "no repeated letter", "contains every letter of abc"). Then the length changes. Every variable window follows the same loop:

1. Grow: move right one step and add the new item to what the window remembers.
2. Shrink while broken: while the window breaks the rule, remove nums[left] from what the window remembers and move left one step.
3. Record: now the window obeys the rule again — compare its length with the best so far.

The promise that makes this correct is called the invariant (a fact that is true every time the program reaches a certain line): after the inner loop, the window [left, right] is always valid, and it is the longest valid window that ends at right. Why the longest? Because left only moves when it must: every start further left was already proven broken (for this right or an earlier, shorter one — and when all numbers are 0 or more, a longer window that contains a broken one is broken too).

Why a loop inside a loop is still O(n)

The code above has a while inside a for, which usually smells like O(n²). Count the moves instead of the loops. right moves exactly n times in total. left only ever moves forward and can never pass the end, so over the whole run it moves at most n times — no matter how those moves are spread out. Some steps of right cause no shrinking, one step might cause five, but the total is capped. Every item enters once and leaves at most once: at most 2n moves, O(n). This way of counting the total instead of the worst single step is called amortized analysis — see C17 · Amortized Analysis. The counter under the animation above shows it live.

What the window remembers

The window is only fast if adding or removing one item updates its "memory" in O(1). Pick the smallest thing that answers the question:

Best Time to Buy and Sell Stock

The task. prices[i] is the price of one share on day i. You may buy one share on one day and sell it on a later day — one transaction only. Return the biggest profit you can make. If no later price is higher than an earlier one, do not trade and return 0.

Brute force. Try every buy day with every later sell day and keep the biggest difference: n(n − 1)/2 pairs, O(n²) time.

Key insight. For a fixed sell day, the best buy day is simply the cheapest day before it. So we only need the minimum so far. In window language: the window is [buy, sell]; sell grows every day; buy is the left edge, and it jumps forward to sell whenever a new cheapest day appears.

Why the jump is safe. Suppose day sell is cheaper than day buy. For any future sale, buying at the new cheaper day gives a strictly bigger profit than buying at the old one, so no future answer can start at the old buy or at any day before the new one. Throwing them away loses nothing.

An edge case: the price falls every day. Each day becomes the new cheapest day, the window keeps restarting, and the answer stays 0.

Complexity. Time O(n) — one look at each day. Space O(1) — two indexes and one number.

Follow-ups interviewers ask.

• Any number of trades. Add up every rise from one day to the next — a greedy one-liner, no window needed.
• With a fee per trade, or a rest day after each sale. Now a choice today changes what you may do tomorrow, so a window is not enough: these need dynamic programming with a few running states (questions p03-q19 and p03-q20 in the bank; DP is taught in C15 · Dynamic Programming).
• Return the days, not just the profit. Remember buy and sell whenever best improves (the animation does this).

The idea underneath: a running minimum is the simplest thing a window can remember — the same "keep a running answer" spirit as the prefix maxima of Step 13.2 · Trapping Rain Water.

Longest Substring Without Repeating Characters

The task. Given a string s, return the length of the longest substring (a contiguous piece of s) in which no character appears twice. Every character counts, including spaces and digits, and capital and small letters are different characters.

Brute force. For every start, extend the end until a character repeats (checking with a Set): O(n²) time in the worst case, and it repeats the same work for neighbouring starts.

Key insight. Keep the window [left, right] free of repeats. When s[right] is already inside the window at position p, no window that still contains position p can include right, so left may jump straight to p + 1 instead of creeping one step at a time. A map lastSeen (character → the last index where it appeared, built on Dart's Map from D27 · Set & Map methods) finds p in O(1).

Why the jump is safe — and the one trap. Every start between the old left and p still contains both copies, so none of them can be part of a clean window ending at right. The trap: lastSeen is never cleaned, so it may remember a position that is already left of the window. That old copy is not in the window and must be ignored — hence the check lastSeen[c] ≥ left. Without it, left could jump backwards.

An edge case: every character is the same. Each new character finds its twin at the very previous position, so the window keeps jumping and never grows past length 1.

Complexity. Time O(n) — right visits each character once and left only jumps forward. Space O(min(n, alphabet)) for the map (at most 95 printable ASCII characters).

Follow-ups interviewers ask. At most k different characters (p03-q13), at most two kinds — the "fruit baskets" story (p03-q14), the shortest piece containing every kind of character (p03-q24). Return the substring itself (remember left when best improves). Full Unicode text: walk over runes instead of code units (D24 · String methods).

The ideas underneath: hash maps (C11 · Hash Tables) and the "have I seen this before?" pattern of Step 13.1 · Contains Duplicate.

Longest Repeating Character Replacement

The task. You get a string s of capital letters A–Z and a whole number k. You may change at most k letters into any other capital letters. Return the length of the longest substring that can be made of one single repeated letter.

Brute force. For every substring, count its letters and check length − top count ≤ k: O(n²) substrings even with running counts.

Key insight. A window is fixable when (right − left + 1) − maxFreq ≤ k, where maxFreq is the count of its most common letter. Grow right; when the window is not fixable, move left one step. Because we only care about the longest answer, the window never needs to get shorter: once we have found a fixable window of length L, a shorter window cannot beat it. So when the window breaks, we slide it (left and right both move by one) instead of shrinking it. The window's length is then always the best length found so far.

Why maxFreq never needs to go down. When a letter leaves, the true top count inside the window may drop, but we keep the old maxFreq. That looks wrong, but think about when the answer can improve: only when some letter appears more than maxFreq times inside a window — and then maxFreq grows honestly at that moment. A too-high maxFreq only lets the window slide (keeping the old best length) when strictly it is not fixable; it never makes best bigger than a real answer. So recounting the 26 letters after every slide would be wasted work.

An edge case: k = 0, so no paint at all. The answer is the longest run of one letter, and the window slides whenever a different letter enters.

Complexity. Time O(n) — each step does O(1) work (no recount of 26 letters). Space O(1) — at most 26 counters.

Follow-ups interviewers ask. Binary version: the longest run of 1s if you may flip at most k zeros (p03-q8) — the same window with "number of zeros" in place of "length − maxFreq". Delete exactly one item instead (p03-q9). Return which letter and where (store left and the top letter when best improves).

The ideas underneath: counting with a map, as in Step 13.1 · Valid Anagram and Top K Frequent.

Permutation in String

The task. You get two strings of small letters a–z: a short pattern and a longer text. A permutation of the pattern is any rearrangement of its letters ("ten", "net", "nte", …). Return true if some contiguous piece of text is a permutation of pattern, otherwise false.

Brute force. For every piece of length m, sort it and compare with the sorted pattern: O(n·m log m). Or count its letters from scratch: O(n·m).

Key insight. Every candidate has the same length m, so this is a fixed-size window. Keep need (letter counts of the pattern), have (letter counts of the window) and matches (how many of the 26 letters have need = have). When a letter enters, only its own count changes, so only its agreement can flip: if have just reached need, one more letter agrees; if have just went one past need, a letter that agreed stops agreeing. Leaving works the same way in reverse.

Why it is correct. matches = 26 means every letter count agrees, which is exactly "the window is a rearrangement of the pattern". Each update changes one count by 1, and the two if checks are the only two ways that change can flip agreement, so matches is always the true count.

An edge case with no valid window: the window slides all the way to the end, matches never reaches 26, and the answer is false.

Complexity. Time O(n + 26) = O(n) — one initial count, one 26-letter scan, then O(1) per slide. Space O(1) — two lists of 26.

Follow-ups interviewers ask. Return every start position of a rearrangement (p03-q10 — the same window, collecting starts instead of stopping). Allow any characters, not just a–z (use a Map instead of 26 boxes). What if the pattern is huge and the text arrives as a stream? The window only needs the last m characters, so a queue of size m is enough.

The idea underneath: letter counts as a fingerprint, from Step 13.1 · Valid Anagram and Group Anagrams.

Minimum Window Substring

The task. You get two strings s and t. Return the shortest contiguous piece of s that contains every character of t, including repeats (if t has two A's, the piece needs at least two A's). Order does not matter, and extra characters are allowed. If no piece works, return the empty string "". If several shortest pieces exist, return the one that starts first. Capital and small letters are different.

Brute force. Check every piece s[i..j] with fresh counts: O(n²) pieces, each O(n) or O(alphabet) to check.

Key insight. This is the shortest-window version of the template: grow until the window is valid, then shrink while it stays valid, recording each valid length. Keep need (counts from t), have (counts in the window) and formed = how many different characters of t already have have[c] ≥ need[c]. The window is valid exactly when formed equals the number of different characters in t. As in Permutation in String, one entering or leaving character can change formed by at most one, so the validity test is O(1).

Why shrinking is safe. For a fixed right, once [left, right] is valid, any window starting further left is longer, so it cannot be the answer for this right. And once shrinking breaks validity, any start further right is also invalid for this right (it holds even fewer characters). So for each right the loop checks exactly the one window that matters: the shortest valid one ending there.

An edge case with no valid window: t needs two a's and s has one, so formed never reaches the goal and the answer is "".

Complexity. Time O(|s| + |t|) — right and left each pass over s once, and t is counted once. Space O(k) for the two maps, k = number of different characters.

Follow-ups interviewers ask. Order matters (the piece must contain t as a subsequence): a forward-then-backward scan, p03-q31. The shortest piece containing every kind of character of s itself (p03-q24). Count how many valid windows exist (for each right, every start up to the first invalid one counts — the "at most" counting trick of p03-q16).

The ideas underneath: counting maps from Step 13.1, and the same-direction pointers of Step 13.2.

Sliding Window Maximum

The task. You get a list of whole numbers nums and a window length k. A window of length k slides from the left end to the right end, one step at a time. Return the biggest number inside each window, in order. If k is bigger than the list, there is no full window and the answer is empty.

Brute force. For each of the n − k + 1 windows, scan its k numbers for the biggest: O(n·k). A max-heap of the window gives O(n log k) — better, but deletion of the leaving number is awkward.

Key insight. A monotonic deque: a double-ended queue (you can add or remove at both ends in O(1); Dart's ListQueue from D28 · Queue, ListQueue & LinkedList) holding indexes whose values decrease from front to back. When nums[right] arrives, pop from the back every index whose value is ≤ it — those can never be a maximum again, because right is newer (stays longer) and at least as big. Then push right. If the front index has slid out of the window (≤ right − k), pop it from the front. The front is now the window's maximum.

Why we store indexes, not values. To know whether the front has left the window we need its position. With equal values stored as values, we could not tell which copy expired.

An edge case: all numbers equal. Because the pop rule uses ≤, each new 3 removes the older 3, so the deque holds just one index and nothing ever needs to expire from the front.

Complexity. Time O(n) — every index is pushed once and popped at most once (from the back or the front), the same "enters once, leaves once" count as the opening section; the inner while cannot pop more items than were pushed. Space O(k) for the deque, plus the output.

Follow-ups interviewers ask. Window minimum (flip the comparison). Longest window whose max − min ≤ limit: two deques at once (p03-q23), and counting such windows (p03-q30). Window median: a deque cannot do it — keep the window sorted or use two heaps (p03-q26; heaps are in C06 · Heapsort). A dynamic-programming recurrence that needs "the best of the last k values" uses this same deque (p03-q28).

The ideas underneath: queues and deques (D28, C10 · Elementary Data Structures) and amortized counting (C17 · Amortized Analysis).

Quiz

Interview questions

Variations and follow-ups of the six problems above — the questions interviewers move to once you have solved the classic version, plus two stock problems that look like windows but need dynamic programming. Every solution is tested in Dart on its examples and on hundreds of random inputs against a slow reference.

Cheat sheet

A window needs a contiguous piece and a rule where shrinking moves toward valid (true for counts and for sums of non-negative numbers). With negative numbers use prefix sums with a map (Step 13.1 · Arrays & Hashing); for pairs in a sorted list use opposite-end pointers (Step 13.2 · Two Pointers).