Algorithm

Flatten Nested List Iterator

Stacks & Queues Pattern

Flatten Nested List Iterator

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 nestedList) initializes the iterator with the nested list. int next() returns the next integer. boolean hasNext() returns true if there are still some integers in the nested list.

CONSTRAINTS
  • 1 <= nestedList.length <= 500
  • -10⁶ <= integers in the list <= 10⁶
  • Nesting depth can be arbitrary
  • next() and hasNext() must run in O(1) amortized
EXAMPLE 1
Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
DFS order: expand [1,1]->1,1; then integer 2; then expand [1,1]->1,1.
EXAMPLE 2
Input: [1,[4,[6]]]
Output: [1,4,6]
1 first; expand [4,[6]]->4 then expand [6]->6.
EXAMPLE 3
Input: [[]]
Output: []
Empty sublists are unwrapped and discarded in hasNext() until an integer is found.
What if there is a list containing only empty lists?
The hasNext() loop will keep popping empty lists until the stack is completely empty, then it will return False. It correctly skips all 'empty' depth.

Take [[1, 2], 3]. The first element is a list, not a number, so you can't hand it over directly — you open it first, find 1 and 2, but must not lose track of the 3 still waiting behind it. You want to fully explore the current box before returning to whatever sits after it, always coming back to the item you set aside most recently.

"Handle the most recently set-aside item first" is what a stack does: a pile touched only from the top, with push (add on top) and pop (take the top), last-in-first-out. Keep everything left to process on a stack, the next thing to look at on top.

The one twist: push in reverse. A stack flips order, so if you push the top-level items back-to-front, the first element of the list ends up on top — the order the caller expects.
- The constructor pushes every top-level item onto the stack in reverse.
- hasNext() does the real work. Peek the top. If it's an integer, you're ready → true. If it's a list, pop it and push its elements back on (reversed again), then look again. Repeat until an integer surfaces or the stack empties (→ false). Empty sub-lists simply vanish during this unwrapping.
- next() relies on hasNext() having already surfaced an integer, so it just pops and returns it.

python
class NestedIterator:
    def __init__(self, nestedList):
        self.stack = nestedList[::-1]      # reversed: first element ends up on top

    def hasNext(self):
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True
            self.stack.pop()               # it's a list: unwrap one level
            self.stack.extend(top.getList()[::-1])
        return False

    def next(self):
        return self.stack.pop().getInteger()   # hasNext() guaranteed an int on top
Crucial Noteall the unwrapping lives in hasNext(), and it only ever unwraps one integer's worth at a time — it stops the moment an integer reaches the top, leaving deeper boxes untouched until later. That laziness is why next()/hasNext() are O(1) amortized: each element is pushed and popped exactly once across the whole traversal, not all up front. Always call hasNext() before next() so an integer is guaranteed on top.
Worked Example:[[1, 2], 3]
- Init: push reversed → [3, [1,2]] (top is [1,2])
- hasNext(): top is a list → pop, push 2 then 1 → [3, 2, 1]; top is 1 → true
- next() → 1 · next() → 2 · hasNext(): top 3 is an int → next() → 3
- Order: 1, 2, 3

This is really depth-first traversal driven by an explicit stack instead of recursion — the stack remembers the branches you haven't visited yet while you go deep into the current one. Any "walk a nested structure lazily" task leans on the same move.

Interactive Strategy Visualization
ITERATOR DFS INSIGHT

Lazy Tree Flattening via Manual Stack

List[3]
FLATTENING STACK
Current State
I
LAST OPERATIONINIT
Strategy Execution

Start with the entire nested list as a single token on the stack.

Amortized O(1) Performance

By only flattening when next() is called, we avoid the O(N) cost of pre-flattening the entire structure.

O(N) Flatten Everything Upfront
→
O(1) Amortized Lazy Stack Unwrap