Flatten Nested List Iterator — Stack-Based Lazy Traversal

Problem Statement#

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

• NestedIterator(List<NestedInteger> nestedList) Initializes the iterator.
• int next() Returns the next integer in the nested list.
• boolean hasNext() Returns true if there are still some integers in the nested list, otherwise false.

The implementation must support iterators correctly: hasNext() should not consume an element, and repeated calls should be idempotent up to the next next().

Constraints:

• 1 <= nestedList.length <= 500
• The values of integers are in the range [-10^6, 10^6].

Input:  nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]

Input:  nestedList = [1,[4,[6]]]
Output: [1,4,6]

Why This Problem Matters#

LeetCode 341 Flatten Nested List Iterator is a classic FAANG design question, especially popular at Google, Meta, and Amazon. It tests three things at once: iterator interface design, stack-based lazy traversal, and the nuance of idempotent hasNext. The trap of eagerly flattening the structure into a flat list trades O(n) space for unnecessary upfront cost — bad if the consumer reads only the first few elements or if the structure is large.

Lazy iterators are everywhere in production: streaming JSON parsers, database cursors, infinite generators, paginated APIs. This problem is the smallest example that captures all the subtleties of lazy traversal with arbitrary nesting depth, which is why interviewers reach for it so often.

The Core Insight#

Use a stack to simulate the call stack of a recursive flattener, but advance lazily. The stack stores either iterators or list snapshots; each pop processes one nested layer.

Two clean designs:

1. Stack of (list, index) pairs. Each frame represents a partial traversal of a sublist. Push a new frame whenever you encounter a nested list; pop when you exhaust a frame. Top of stack always points to the next element to consider.
2. Lazy normalization. hasNext flattens the stack just enough so that the top is an integer. next then pops that integer. This keeps next trivial.

The second approach is cleaner because it puts all the logic in hasNext, which is allowed to mutate state (the iterator contract permits it). next then becomes a pure read.

Visual Dry Run#

nestedList equals [1, [4, [6]]].

After init, push elements in reverse onto the stack so the leftmost is on top:

Stack (top first): 1, [4, [6]]

Call hasNext. Top is integer 1. Return true. Call next. Pop 1. Return 1. Stack now: [4, [6]].

Call hasNext. Top is a list [4, [6]]. Pop it, push its elements in reverse: 4, [6]. Top is now 4. Return true. Call next. Pop 4. Return 4. Stack now: [6].

Call hasNext. Top is list [6]. Pop, push 6. Top is 6. Return true. Call next. Pop 6. Return 6. Stack now empty.

Call hasNext. Stack empty. Return false. Iteration complete: [1, 4, 6].

Solution (Optimal)#

We push elements in reverse so the leftmost is on top. hasNext lazily expands lists until the top is an integer.

class NestedIterator:
    def __init__(self, nestedList):
        self.stack = []
        # push in reverse so the first element is on top
        for item in reversed(nestedList):
            self.stack.append(item)
 
    def next(self) -> int:
        self.hasNext()
        return self.stack.pop().getInteger()
 
    def hasNext(self) -> bool:
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True
            self.stack.pop()
            for item in reversed(top.getList()):
                self.stack.append(item)
        return False

class NestedIterator {
  constructor(nestedList) {
    this.stack = [];
    for (let i = nestedList.length - 1; i >= 0; i--) {
      this.stack.push(nestedList[i]);
    }
  }
 
  next() {
    this.hasNext();
    return this.stack.pop().getInteger();
  }
 
  hasNext() {
    while (this.stack.length) {
      const top = this.stack[this.stack.length - 1];
      if (top.isInteger()) return true;
      this.stack.pop();
      const list = top.getList();
      for (let i = list.length - 1; i >= 0; i--) {
        this.stack.push(list[i]);
      }
    }
    return false;
  }
}

Complexity. hasNext is amortized O(1): each list element is pushed and popped exactly once across the whole iteration. next is also amortized O(1). Initialization is O(top-level length). Space is O(d times w) where d is max nesting depth and w is the max list width — bounded by total element count in the worst case.

Common Mistakes#

• Eagerly flattening into a regular list in the constructor. This loses the lazy benefit and uses unnecessary space.
• Pushing list elements in the original order — this reverses the iteration order. Always push in reverse so the leftmost ends up on top.
• Putting all the logic in next and leaving hasNext as a placeholder. hasNext must be safe to call repeatedly without consuming — that means it must do the lazy expansion.
• Forgetting that an element can itself be an empty list. The while loop in hasNext handles this gracefully because it keeps expanding until it finds an integer or empties the stack.
• Confusing isInteger with truthiness. Use the API as given.

Interview Tips#

• Begin by clarifying the iterator contract: hasNext is idempotent, next mutates state and returns the next integer.
• Explicitly reject the eager-flatten approach with a one-liner: "I want to avoid pre-flattening because the consumer might only read a prefix."
• Walk through the stack invariant on the whiteboard: after hasNext returns true, the top is always an integer.
• Discuss the trade-off between stacks of (list, index) tuples versus pushing items reversed. The latter is simpler and equally efficient.
• Mention production analogies: SAX-style XML parsers, JSON streaming, IEnumerable LINQ in .NET.

Follow-up Questions#

1. What if the structure can be infinite (e.g., generated lazily)? Stop pushing all elements eagerly; use lazy generators per level.
2. What if you need a peek operation? Add peek() that returns hasNext-resolved top without popping.
3. How would you reset the iterator? Save the original nestedList reference and re-seed the stack on reset.
4. What if multiple threads call hasNext and next? Wrap with a lock or design a thread-safe variant; the amortized cost may worsen.
5. What if elements include strings or arbitrary types? Generalize NestedInteger to a tagged union; the stack pattern is unchanged.

Key Takeaways#

• A stack-based lazy iterator gives amortized O(1) per element with bounded space.
• Push children in reverse so leftmost is on top — this preserves iteration order.
• Put expansion logic in hasNext to keep it idempotent and next trivial.
• Mark "ready" state by ensuring the stack top is always an integer after hasNext returns true.
• Avoid eager flattening unless the consumer truly needs all elements — laziness saves memory and CPU.
• This pattern generalizes to any nested or recursive data structure traversal.