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.

If you have a list like [[1, 2], 3], you can't just hand the user the first item because the first item is a box [1, 2], not a number. You have to open that box first. But after you open it and find the 1 and 2, you must not forget that the 3 is still waiting for its turn at the end.

This is why we use a Stack. It acts like a Priority Pile. When we see a box, we "explode" it and put all its contents back on the top of our pile. The items that were already at the bottom of the pile (like the 3) just stay there, waiting patiently while we focus on the new items we just found. This allows us to dig as deep as we need into nested boxes without losing our place in the rest of the list.

Exploding the Boxes

- 1. The Priority Pile: We start by putting all the top-level items (boxes or numbers) onto our Stack. But there is a trick: we push them in reverse order. This ensures the first item in the list is at the very top of the stack, ready to be inspected first.
- 2. The hasNext() Inspection: This is where the magic happens. Before we give the user a number, we look at the top of the Stack:
- If it's a number: We are done! The iterator is ready.
- If it's a box: We "explode" it — Pop it open and put its immediate contents back onto the stack (again, in reverse order). This brings the inner-most numbers one step closer to the top.
- We repeat this until a number finally reaches the top of the stack.
- 3. The next() Reveal: Since hasNext() guaranteed that a number is sitting at the top, we just Pop it and hand it to the user.

Code Blueprint
text
CLASS NestedIterator:
    stack = []

    CONSTRUCTOR(nestedList):
        // Push in reverse to keep first item on top
        FOR i from nestedList.length - 1 down to 0:
            stack.PUSH(nestedList[i])

    FUNCTION hasNext():
        // Keep unwrapping until we find an integer
        WHILE stack is NOT empty:
            top = stack.PEEK()
            IF top is Integer:
                RETURN True
            
            // It's a list! Unwrap one level.
            stack.POP()
            innerList = top.getList()
            FOR i from innerList.length - 1 down to 0:
                stack.PUSH(innerList[i])
        
        RETURN False

    FUNCTION next():
        RETURN stack.POP()
Worked Example:[[1, 2], 3]
0
3
1
[1, 2]
Top
Constructor: Push list elements in reverse (right to left). Stack = [3, [1, 2]]. Top of stack is list [1, 2].
0
3
1
2
2
1
Top
hasNext(): Top of stack is a nested list [1, 2]. Pop it, and push its sub-elements in reverse order: 2 then 1. Top is now integer 1. Return true.
0
3
1
2
Top
next(): Pop and return 1. Stack is now [3, 2]. Top of stack is integer 2.
0
3
Top
next(): Pop and return 2. Stack is now [3]. Top of stack is integer 3.
next(): Pop and return 3. Stack is empty. Traversal complete!
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