Iterators
What is this?
An iterator is a little device that hands you the next item in a sequence each time you ask, without ever laying out the whole sequence at once. Picture a Pez dispenser: it gives you one candy per click and keeps the rest tucked away. The design trick is to hold just enough state — a pointer or two, a small stack — so you can always produce the next item on demand and know when you've run out.
💡 Fun fact: This lazy, one-at-a-time style is how huge data pipelines stay fast — tools like Python generators and database cursors stream billions of rows without ever loading them all into memory, producing each row only at the moment you ask for it.
🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: An iterator exposes a sequence one element at a time via
next()/hasNext()— without ever building the whole sequence in memory. The design challenge is holding just enough state (a stack, a pair of pointers, a run index) to produce the next element on demand, and maintaining one clear invariant between calls.
Lazy beats eager
The naive move is to flatten everything up front in the constructor, then index it — but that defeats the purpose: O(total) memory, and pointless if the caller stops early. A real iterator keeps a small cursor and computes the next element only when asked:
The recurring trick is an invariant maintained by a helper: after construction and after every next(), the cursor sits on a valid element (or past the end). One _advance()/_push_left() routine enforces it; everything else falls out.
The three problems
| Problem | State held | Invariant |
|---|---|---|
| Binary Search Tree Iterator | a stack of un-yielded ancestors | the stack top is the next-smallest; O(h) space, amortized O(1) next |
| RLE Iterator | index into the runs + remaining count | consume from runs lazily; never expand the decoded sequence |
| Flatten 2D Vector | (outer, inner) pointers + _advance() |
the cursor always rests on a real element or off the end (skip empty inner lists) |
Each one is a different shape of "produce the next element with bounded state": a tree (defer the right subtree via a stack), compressed data (walk runs without decompressing), and a jagged collection (two pointers that skip gaps).
The pattern
Decide the minimal state that lets you produce the next element, then write one helper that re-establishes the "cursor is valid" invariant after each call.
hasNext()is "is the cursor valid?";next()returns the current element and advances. Each element is touched O(1) amortized — the deferred work (pushing a left spine, skipping empties) averages out.
📓 Draw it yourself
- The breathing stack. For the BST iterator, draw the stack holding the leftmost-spine; pop on
next(), then push the left spine of the popped node's right child. - Skip the empties. For Flatten 2D Vector, draw rows with some empty inner lists and an
_advance()that hops the cursor over them to the next real element.
Snap photos and embed them with the /host-diagrams skill.
Key takeaways
- Lazy, not eager: hold a small cursor; never pre-materialize the whole sequence.
- One invariant, one helper: "the cursor is on a valid next element," re-established by
_advance()/stack-push after each call. - Amortized O(1): deferred work (left-spine pushes, empty-list skips) averages to constant per
next(); space is O(state), not O(n). - Same idea, three shapes: tree (stack), compressed runs (run index), jagged 2-D (two pointers).
- Why interviewers like it: iterators test whether you reason about state between calls and laziness — the core of streaming and cursor APIs.
Order: Binary Search Tree Iterator → RLE Iterator → Flatten 2D Vector.