Why a window with a nested loop is still O(n)

Sliding window Mid-level Python 3.13+ Reviewed 1 Nov 2026 By Best Latest Apps

Predict the output

This counts the inner-loop steps of a window. What does it print?

Python 3.13

spend, budget = [3] * 10, 5
total = left = inner = 0
for right, x in enumerate(spend):
    total += x
    while total > budget:
        total -= spend[left]
        left += 1
        inner += 1
print(inner, left)

Options9 945 910 10

Choose an answer, then open Show answer below to check it.

Show answer

Answer: A 9 9

Right: each step after the first drops exactly one day, nine times in all.

Inner steps equal left-pointer moves, and the left pointer can move at most n times in total.

Why not the others?

B 45 9. The inner loop does not rescan the window; it runs once per new day here.
C 10 10. The left pointer stays one behind the right pointer, ending at 9.

30-second answer

Count pointer moves instead of loop iterations. The right pointer moves n times in the for loop; the left pointer only moves forward and never past the right, so across the whole run it moves at most n times. Total work is O(2n) = O(n). This is an amortised argument: one step can do a lot, but the total is bounded.

Practise saying it · 45 s. No recording, just a timer

Explain the amortised argument for sliding windows.

Say your answer out loud, then check which of these points you covered:

Count pointer moves
Left moves at most n times
O(n) total

Deep dive

Amortised O(1) per step: the expensive shrinks are paid for by the earlier grows.

The same argument covers monotonic stacks and deques: each item is pushed once and popped at most once.

If the left pointer could move backwards, the bound would fail.

Common mistakes

Multiplying the loop bounds and calling it O(n²).
Resetting the left pointer to the right pointer's position (that is still fine) versus resetting it to 0 (that is quadratic).

Senior take & follow-ups

Use the phrase 'each element enters and leaves the window at most once'. It is the standard proof.

Follow-up questions

Think of your answer first, then open the hint.

What is amortised analysis?
Show hint
Bounding the total cost of a sequence of operations rather than the worst single one.
Where else does this show up?
Show hint
Dynamic array appends, union-find, and stack-based scans.

What each operation costs: Arrays · Deque

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.