AdvancedHabits & complexity
Why some “nested loops” are still O(n)
Count total work, not loop nesting. If each element enters and leaves a stack or window once, the whole thing is O(n).
The idea
A while loop inside a for loop looks like O(n²), but what matters is how many times the inner loop runs in total. In a sliding window or monotonic stack, each element is added once and removed at most once: 2n operations overall.
Dynamic arrays use the same idea: occasional O(n) resizes average out to O(1) per append.
Worked example
Daily Temperatures with a stack
- The inner while pops indices.
- Each index is pushed once and popped at most once.
- So across the whole run there are at most n pops: O(n) total, even though one step can pop many.
How to spot it
- Two pointers that only move forward, monotonic stacks and deques, union-find, dynamic arrays.
Common mistakes
- Calling these O(n²) in an interview: explain the total-work argument instead.
- Assuming every inner loop is amortized: if the inner pointer can move backwards, it isn't.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →