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.
Flatten 2D Vector
Core idea: Keep two cursors — an outer index and an inner index — and a tiny
_advance()helper that skips past exhausted and empty inner lists, so the pair always rests on a real element or just past the end.
Problem, rephrased
Picture a warehouse organized into shelves. Each shelf is a list of boxes, and a shelf can be empty (it exists, but nothing is on it). A picker walks the shelves left to right, and within each shelf grabs boxes left to right. You hand the picker the whole warehouse and ask for a simple machine with two buttons:
next()— give me the next box and step forward.has_next()— is there any box left to grab?
The catch: empty shelves must be stepped over silently. The picker should never stall on an empty shelf, never hand you a box from a shelf that has none, and never copy all the boxes into one big pile up front — they should walk lazily, only moving when you press a button.
Formally: build Vector2D(vec) over a list of lists. next() returns the next element in row-major order; has_next() returns whether any element remains. Empty inner lists are allowed and must be skipped.
Here's a session over vec = [[1, 2], [], [3], [], [], [4]]:
| Operation | Returns | Cursor (outer, inner) after |
|---|---|---|
Vector2D([[1,2],[],[3],[],[],[4]]) |
— | (0, 0) — already on 1 |
has_next() |
True |
(0, 0) |
next() |
1 |
(0, 1) |
next() |
2 |
(2, 0) — skipped empty row 1 |
next() |
3 |
(5, 0) — skipped empty rows 3 & 4 |
has_next() |
True |
(5, 0) |
next() |
4 |
(6, 0) — off the end |
has_next() |
False |
(6, 0) |
Notice has_next() returns the same answer no matter how many times you call it — it never consumes anything.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson