Iterator

Topic Type: Data Structure — a stateful object that exposes a sequential access API over an underlying collection or computation.

LeetCode tag size: ~35–50 problems. Depth: core concepts, main patterns, key complexities.

---

1. Core Concepts

Iterator — an object that produces elements one at a time on demand, maintaining a cursor into an underlying sequence. Separates traversal logic from collection structure.

Iterator protocol — the minimal API: next() returns the next element and advances the cursor; hasNext() returns whether any elements remain. Some variants add peek() without advancing.

Lazy evaluation — elements are computed or fetched only when next() is called, not upfront. Enables iterating over infinite or very large sequences with O(1) space per step.

External iterator — the caller controls traversal by explicitly calling next(). Enables interleaving multiple iterators (zip, merge) and peeking without consuming.

Internal iterator — traversal is controlled by the collection (e.g., Python for x in collection). Not directly composable with other iterators.

Peeking — reading the next element without consuming it. Requires buffering exactly one element. Used in merge logic to compare heads of multiple iterators.

Flattening — converting a nested or two-dimensional structure into a linear sequence. Depth-first by default; requires a stack or recursion to defer inner iterators.

Buffering / prefetch — storing one or more pre-fetched elements to support peek() or hasNext() when the underlying source is consumed-on-read (e.g., a generator or file stream).

Exhaustion — the state when hasNext() returns False. Once exhausted, calling next() is undefined behavior in most designs; guard with hasNext() first.

Composite / wrapping iterator — an iterator built on top of one or more existing iterators. The outer iterator holds references to inner iterators and delegates element production to them.

---

2. Structural Invariants

---

3. Internal Representation

Single iterator with peek buffer:

self._buffer = None   # None means no buffered element
self._exhausted = False

hasNext() tries to fill the buffer from the underlying source if empty; next() drains the buffer first.

Flatten with explicit stack: Store a stack of iterators. The top entry is the currently-active iterator. When it exhausts, pop and resume the parent. This mirrors the call stack of recursion but makes state explicit and restartable.

Flatten via generator (yield from): Python generators maintain their own frame as the cursor. yield from inner flattens one level; nesting yield from calls recursively flattens arbitrarily deep structures. The generator frame is the buffer.

k-way merge with min-heap: Store (value, iterator_index) tuples in a heap. The heap maintains the globally-smallest unread element at the top. When popped, the same iterator advances and re-inserts its next element.

Compressed / encoded iterator (RLE, combination): Internal state includes the current segment (value + remaining count) or a combinatorial index. next() decrements a counter or increments an index before yielding.

---

4. Types / Variants

---

5. Topic-Specific Operations

__init__(source) — initialise internal state (stack, buffer, heap). May advance the underlying source to position the cursor at the first valid element. For flatten, push the outermost iterator; for merge, heapify initial elements.

hasNext() → bool — determine whether any unconsumed element exists. For peek-buffered designs, attempt to fill the buffer here; return whether the buffer is non-empty. Must not mutate visible state. O(1) amortised (may do work lazily).

next() → element — return and consume the current element; advance cursor to the next. If a peek buffer exists, drain it first. For flatten, advance the top-of-stack iterator; if it exhausts, pop and continue. O(1) amortised for most designs; O(log k) for k-way merge.

peek() → element — return the next element without consuming it. If buffer is empty, call next() on the underlying source and store the result. Subsequent calls return the buffer. Edge case: calling peek() on an exhausted iterator is undefined — always guard with hasNext().

---

6. Key Algorithms

Peek Buffer (one-element lookahead)

Wraps an existing iterator to add peek(). Maintains a _peeked flag and _val cache; next() checks the flag first.

# inside next():
if self._peeked:
    self._peeked = False; return self._val
return iter(self._source).__next__()

Time: O(1) per operation. Space: O(1) buffer.

Flatten with Stack (iterative DFS)

Solves LeetCode 341 (Flatten Nested List Iterator). Push the top-level iterator onto a stack. hasNext() advances the stack until the front element is an integer.

# inside hasNext():
while stack and not stack[-1].isInteger():
    stack.extend(stack.pop().getList())

Time: O(1) amortised per next() call (each element processed once). Space: O(d) where d is nesting depth.

Flatten with Generator

Uses Python yield from for clean recursive flattening. The generator frame stores cursor state automatically.

def _gen(lst):
    for item in lst:
        yield from _gen(item) if isinstance(item, list) else [item]

Time: O(n) total. Space: O(d) call stack depth. Preferred for nested arbitrary structures when Python is available.

k-Way Merge via Min-Heap

Merges k sorted iterators. Push (first_value, i, iterator_i) for each iterator. Pop min, yield it, push the next from the same iterator.

heapq.heappush(heap, (val, i, it))
val, i, it = heapq.heappop(heap)

Time: O(n log k) for n total elements across k iterators. Space: O(k) heap.

Zigzag / Round-Robin Merge

Maintains a queue of iterators. On each next(), pop from the front, yield its next element, push back if not exhausted.

it = deque.popleft()
val = next(it)
if has_more(it): deque.append(it)

Time: O(1) per element. Space: O(k) queue.

BST Iterator (Controlled In-Order)

Maintains an explicit stack simulating the recursive call stack. hasNext() checks if stack is non-empty; next() pops and pushes right subtree's leftmost spine.

# push leftmost spine on init; in next():
node = stack.pop(); push_left(node.right)

Time: O(h) space for the stack; O(1) amortised per call (each node pushed/popped once).

See binary-search-tree.md for full BST traversal coverage.

RLE / Compressed Iterator

Track (current_value, remaining_count). next() decrements count; when count hits 0, advance to the next encoded segment.

Time: O(1) per next(). Space: O(1).

---

7. Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

8. Common Patterns

---

9. Edge Cases & Pitfalls

• Calling next() without hasNext(): Most iterator designs leave this undefined or raise an exception. Interviewers expect you to guard; always call hasNext() before next() in the driver loop.

• hasNext() has side effects: A common bug is placing cursor-advancing logic in next() only, making hasNext() unreliable. Move the "find next valid element" logic into hasNext() so it is idempotent after the first call.

• Double-consuming the buffer: In a peek wrapper, forgetting to clear the buffer after next() consumes it causes the same element to be returned twice. Always clear _peeked = False before returning.

• Empty iterator on peek(): Calling peek() on an exhausted iterator crashes unless guarded. Always check hasNext() before peek().

• Stack underflow in flatten: If the outer list is empty or all sublists are empty, the stack may be empty when next() is called. hasNext() must return False in this case; next() must never be called.

• Heap tie-breaking with non-comparable iterators: heapq compares tuple elements left to right. If two values are equal, Python will try to compare the iterator object, which raises TypeError. Use a tie-break integer index: (val, idx, iterator).

• Mutation of the underlying collection during iteration: Modifying the list being iterated (appending, removing) while an iterator is active invalidates the cursor. Avoid; or snapshot the list on construction.

• Off-by-one in RLE iterator: When count reaches 0, the iterator must advance to the next segment before checking hasNext(). Forgetting this yields one extra element or miscounts.

• Generator exhaustion is silent: A Python generator that returns None when exhausted won't raise StopIteration until the frame is done. Wrap with try/except StopIteration or use next(gen, sentinel) to detect exhaustion.

• BST iterator right-subtree push: After popping a node and yielding it, push the leftmost spine of node.right, not node.right itself. Pushing node.right directly breaks in-order order.

---

10. Implementation Notes

• Python iter() and next() builtins work with any object implementing __iter__ and __next__; use next(it, default) to avoid StopIteration exceptions when consuming unknown iterators.

• Python generators are the cleanest iterator implementation: yield suspends the frame, yield from delegates to a sub-generator; the frame itself is the cursor and buffer.

• collections.deque is the correct structure for round-robin rotation; list pop(0) is O(n).

• Python heapq is a min-heap only; for max-heap semantics, negate values or use a wrapper class with __lt__ defined.

• Recursion depth limit in Python is ~1000 by default; for deeply nested flatten problems, use the iterative stack approach to avoid RecursionError.

• When implementing hasNext() with a buffer-fill pattern, ensure the fill attempts exactly once per "slot" to avoid O(n) work per call on sparse iterators.

• In class-based iterator designs, do not store a reference to the original list and iterate by index — this breaks the lazy/streaming contract and wastes memory for large inputs.

---

11. Cross-Topic Relations

---

12. Interview Reference

Must-Know Problems

Foundational (understand the protocol)

• LeetCode 284 — Peeking Iterator (wrap with one-element buffer)
• LeetCode 173 — Binary Search Tree Iterator (lazy spine-push, O(h) space)

Flatten

• LeetCode 341 — Flatten Nested List Iterator (stack of iterators or generator)
• LeetCode 251 — Flatten 2D Vector (two-index cursor or iterator-of-iterators)

Merge / Interleave

• LeetCode 281 — Zigzag Iterator (round-robin deque, two iterators)
• LeetCode 23 — Merge k Sorted Lists (heap-based merge; lists are iterators here)

Compressed / Encoded

• LeetCode 900 — RLE Iterator (segment counter with skip logic)
• LeetCode 604 — Design Compressed String Iterator (character + count pair)

Combinatorial

• LeetCode 1286 — Iterator for Combination (lexicographic next-combination)

Clarification Questions to Ask

• "Should next() throw on an exhausted iterator, or is the caller guaranteed to check hasNext() first?"
• "Is the nesting depth bounded, or can it be arbitrarily deep?" (affects stack vs. recursion choice)
• "Are the k input iterators guaranteed sorted, or just non-empty?" (affects whether heap is needed)
• "Should peek() be idempotent — same value returned on repeated calls without next()?"
• "Is the iterator expected to handle an empty input on construction?"
• "For RLE: can count be zero in the encoded input?" (affects segment-skip logic)

Common Interview Mistakes

• Placing cursor-advancing logic only in next(), causing hasNext() to be stateful and unreliable.
• Forgetting to handle the case where all sublists/inner iterators are empty in a flatten design.
• Using a list index cursor instead of a proper iterator reference, losing the lazy evaluation property.
• Not using a tie-break index in heap entries, causing TypeError when two values are equal.
• In BST iterator, pushing node.right instead of the leftmost spine of node.right.
• Calling next() without checking hasNext() in driver code, causing an exception on empty input.
• Making peek() advance the cursor instead of buffering, so subsequent calls return different values.

Typical Follow-Up Escalations

• "Now support prev() / bidirectional iteration." — Requires a doubly-ended buffer or storing history; note this breaks the lazy property.
• "Now merge k sorted iterators instead of 2." — Extend to a min-heap with (value, index, iterator) tuples.
• "What if the nested list has cycles?" — Add a visited set keyed on object identity; raise or skip on revisit.
• "Make your flatten iterator thread-safe." — Add a mutex around hasNext()/next(); explain the TOCTOU issue between the two calls.
• "Can you do this in O(1) space?" — For flatten: only possible if the nested structure provides parent pointers; otherwise O(d) is optimal.
• "Now skip the first n elements efficiently." — For RLE iterator: subtract n from segment counts without yielding; O(segments) not O(n).