The sliding window

A sliding window is a contiguous range [l, r] plus an invariant it must always satisfy — no repeated character, at most k distinct values, sum below a bound. The right edge advances one step per iteration. Whenever the new element breaks the invariant, the left edge advances until it holds again. That is the entire control structure, and the interesting claim about it is that the inner loop does not make it quadratic.

The shape

l = 0
for r in range(n):
    add(a[r])                 # extend the window to include r
    while violates_invariant():
        remove(a[l])          # give up the leftmost element
        l += 1
    consider(l, r)            # the window [l, r] is valid here

Three obligations, and every sliding-window bug is one of them going wrong:

1. add must update the window's state incrementally, in O(1).
2. The while condition must be a property that shrinking can only fix.
3. consider runs on a window that is valid — after the shrink, not before.

Obligation 2 is the precondition, in the sense the solving loop means it. If removing an element from the left can make the invariant more violated, the loop does not terminate at the right place and the pattern does not apply. "Sum of positive numbers below a bound" shrinks safely; "sum of possibly-negative numbers below a bound" does not, and that single change of constraint is a standard trap.

Why the nested loop is O(n)

The code has a for inside which sits a while, which looks like O(n²) and is the part people distrust. Count the work by pointer movement instead of by loop nesting.

r takes each of the n values exactly once, so it advances n times total. l only ever increases, and it never passes r, so across the whole run it advances at most n times. Every iteration of the inner while advances l by one, so the inner loop's body executes at most n times in total — not n times per outer step.

A window expanding right, breaking its invariant, and shrinking from the left, with each index entered once and left once100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

Total pointer movements ≤ 2n. At n = 10⁵ that is 200,000 steps, roughly 2 milliseconds at 10⁸ simple operations per second, against the 5 × 10⁹ substring-by-substring check that the same problem invites — about 50 seconds. The ratio is not the point; the accounting is. Each index enters the window once and leaves once. That sentence is the proof.

Two things break it, and both are worth checking before you claim linearity:

• A shrink that scans. If restoring the invariant means recomputing over the window (sum(a[l:r+1]), len(set(window))) you have hidden an O(n) call inside the loop and it really is quadratic. This is exactly the library-call trap in complexity by counting.
• A left pointer that moves backwards. If any branch assigns l a smaller value, the amortised argument collapses.

Longest substring without a repeated character

Carry a map from character to the index where it was last seen. When the incoming character was last seen inside the current window, the window must start after that occurrence:

def longest_unique(s: str) -> int:
    last = {}                     # character -> most recent index
    l = best = 0
    for r, ch in enumerate(s):
        if ch in last and last[ch] >= l:
            l = last[ch] + 1      # jump past the previous copy
        last[ch] = r
        best = max(best, r - l + 1)
    return best

On "abcabcbb", index by index:

r	char	l after	window	length
0	a	0	a	1
1	b	0	ab	2
2	c	0	abc	3
3	a	1	bca	3
4	b	2	cab	3
5	c	3	abc	3
6	b	5	cb	2
7	b	7	b	1

The answer is 3. Length at each step is r - l + 1: at r = 3 that is 3 - 1 + 1 = 3; at r = 6, last['b'] is 4 which is ≥ l = 3, so l becomes 5 and the length is 6 - 5 + 1 = 2. Across the eight characters r advanced 8 times and l advanced from 0 to 7 — 15 moves in total, not the 8 × 9 ÷ 2 = 36 substrings a brute force would examine.

The jump form of the left pointer is worth noticing. The while skeleton would step l forward one character at a time removing counts; the last-seen map lets it leap in one assignment. Both are O(n) overall — the leap is simply less bookkeeping.

Fixed size versus variable size

Fixed size k has no invariant to restore, so there is no inner loop. The window is always exactly k wide, and each step adds one element and removes one:

def max_sum_k(a: list[int], k: int) -> int:
    s = sum(a[:k])
    best = s
    for r in range(k, len(a)):
        s += a[r] - a[r - k]      # one add, one remove — O(1)
        best = max(best, s)
    return best

Rebuilding sum(a[r-k+1:r+1]) each step instead would be O(n·k) — at n = 10⁵ and k = 1,000 that is 10⁸ operations rather than 10⁵.

Variable size is the while skeleton above. The question tells you which: "of length k" is fixed; "longest", "shortest", "how many" is variable.

What state the window carries

Whatever the invariant tests, held so both add and remove are O(1):

Invariant	State	Add	Remove
sum below a bound	running total	s += x	s -= x
no repeated element	set, or last-seen map	insert	discard
at most k distinct	counts map + a distinct counter	bump; if it hit 1, distinct += 1	drop; if it hit 0, distinct -= 1
all of a required multiset covered	counts map + a "satisfied" counter	bump, compare against the requirement	mirror

The distinct counter in row three matters: recomputing len(counts) is cheap in Python but recomputing the number of non-zero entries is not, and forgetting to delete a key that fell to zero is the most common way that row silently breaks. Counting subarrays with that state is the subject of at most k, and exactly k.

One invariant does not fit the table: the maximum of the window. Removing the left element can remove the maximum, and finding the new one means a scan. That needs a monotonic deque, not a counter — a sign that "the state updates in O(1)" is a real condition and not a formality.

In an interview

Say the invariant first, in one sentence, and say what shrinking restores: "the window holds at most k distinct values; when the new element pushes it to k + 1, I shrink from the left until it is back to k." Then say the amortised argument before you are asked, because you will be asked: "the inner loop looks quadratic but l only moves forward and never passes r, so it runs at most n times across the whole scan."

The mistake that loses points: recording the answer in the wrong place — best = max(best, r - l + 1) written before the shrink loop rather than after, so a window that violated the invariant gets counted. It passes small examples and fails the moment the first shrink happens.

Check yourself

Someone claims the two-loop window is O(n²) because a while sits inside a for. Answer them in two sentences.

r advances n times and l never decreases and never passes r, so l advances at most n times over the whole run. The inner body therefore executes at most n times in total, giving at most 2n pointer moves — O(n).

The array can contain negative numbers and the invariant is "sum ≤ S". Does the window still work?

No. Removing a negative element from the left increases the sum, so shrinking can make the violation worse and the while has nothing to converge on. Use prefix sums with a map or a different structure instead.

A fixed window of size k = 1,000 over n = 10⁵ elements. Compare recomputing the sum each step against the incremental update.

Recomputing is n × k = 10⁸ operations, about a second. The incremental update is one addition and one subtraction per step, 2 × 10⁵ operations — a factor of 500 apart, from the same loop.