Lazy iterators

32 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

A list can hold numbers or other lists: [[1, 1], 2, [1, 1]]. You are asked to hand out its numbers one at a time, in reading order: 1, 1, 2, 1, 1. The obvious plan is to flatten the whole thing into a plain list first and then hand out from that. It works. But imagine the nested list is enormous and the caller only wants the first three numbers, or the inner lists are produced slowly as they are needed. Flattening everything up front does all the work before the first answer. An iterator should do only as much work as the caller asks for, and it should remember where it stopped.

Build the structure, one piece at a time

Piece one is a cursor: a record of "where the next unreturned element is". For a flat list that is a single index. For a nested list it has to remember a position in the outer list and, inside that, a position in whichever inner list we are in, and so on for deeper nesting. A stack holds exactly that: each level of nesting we are inside is one entry.

Piece two is a lazy way to use the stack. Push the top-level elements in reverse order, so the first element sits on top. Then, whenever someone asks "is there a next?", look at the top: if it is a number, the answer is yes; if it is a list, pop it and push its elements in reverse, and look again. Only lists that are about to be read get unpacked. On the example:

1. Push the outer list reversed. Stack, top first: [1, 1], 2, [1, 1].
2. hasNext: top is a list, so pop it and push its items reversed. Stack: 1, 1, 2, [1, 1]. Top is a number, so yes.
3. next returns 1. Stack: 1, 2, [1, 1].
4. next returns 1. Stack: 2, [1, 1].
5. next returns 2. Stack: [1, 1].
6. hasNext: top is a list, unpack. Stack: 1, 1. Yes.
7. next, next return 1 and 1. Stack empty, hasNext is false.

The same two pieces build every lazy iterator. For a binary search tree, the stack holds the path of ancestors whose left side is done, so next pops a node and then pushes the left spine of its right child. For a run-length string like a3b2, the cursor is the current letter and how many of it remain. For a peeking iterator, keep one extra slot holding the element already fetched but not yet handed out.

Why it is correct

The invariant is that reading the stack from the top gives exactly the elements not yet returned, in order, with lists still folded. Pushing the outer list reversed makes it true at the start. Unpacking a list replaces one entry with its contents in order, which does not change the sequence of numbers the stack represents. Popping a number removes exactly the first unreturned element. So after any sequence of calls, next always returns the next number in reading order, and hasNext is true exactly when some number remains. Empty inner lists are handled by the same rule: unpacking them pushes nothing, and hasNext keeps looking.

Why it is fast

Each number and each list is pushed once and popped once, so the total work over the whole traversal is proportional to the size of the input. A single next call may do more than one pop when it unpacks several nested lists, but that work is charged to the lists being unpacked, each of which is unpacked only once. Spread over all calls, the cost per next is O(1) on average, which is called amortised O(1). The memory is the stack, which holds at most one entry per pending element on the current path, usually much less than the whole input. Flattening up front costs the whole input before the first answer and stores all of it.

How to recognise it in an interview

Cues: "implement an iterator", "next and hasNext", "lazily", "do not flatten up front", "peek". Say: "I will keep a stack as the cursor and unpack only when hasNext looks at a list, so each element is handled once".

Flatten Nested List Iterator is the walk-through above. Binary Search Tree Iterator is the ancestor-stack version, with O(h) memory for a tree of height h. Peeking Iterator wraps any iterator with one cached element so that peek does not consume it.

02The idea in one line

Keep a stack/pointer so next() does O(1) work on average.

Reach for it when: Flatten nested list, BST iterator, peeking iterator, zigzag iterator, compressed string iterator.

Cost: amortised O(1) per next.

03The walk-through, step by step

The video works one example: Flatten [[1,1],2,[1,1]] lazily. These are its captions in order, so you can follow without the video or check a step you missed.

1. Push the list reversed so the first element is on top
2. hasNext(): top is a list, unpack it onto the stack
3. next() → 1
4. next() → 1
5. next() → 2
6. hasNext(): top is a list, unpack it onto the stack
7. next() → 1
8. next() → 1
9. Stack empty: hasNext() is false
10. Each element is pushed and popped once: amortised O(1) per next()

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Design: Hash map + doubly linked list (LRU), Hash map + array for O(1) random, Time-versioned map, Ordered intervals (range module), Streaming data structures.