Problem Statement
Flatten Nested List Iterator
You are given a nested list of integers. Nested means a list can hold plain numbers, but it can also hold other lists, which can hold more lists, and so on, as deep as you want. Your job is to build an iterator that walks through every number in order as if the whole thing were one flat list. An iterator is just an object with two buttons: hasNext() tells you if there is another number waiting, and next() hands you that number and moves forward. The clean way to do this uses a stack. A stack is like a pile of plates: you add a plate to the top, and you take a plate off the top, so the last plate on is the first one off (last in, first out). It fits here because when we crack open a nested list, the part we want to look at next is whatever we just put on top, which is exactly how a stack behaves.
Signals to notice
Brute force first
Flatten everything upfront into a list — O(n) space, wasteful if only a few elements are needed.
The key insight
Stack-based lazy iteration: push elements in reverse. On hasNext(), unpack lists on top of stack (push their elements in reverse) until an integer is on top. O(1) amortized per call.
Trace it on nestedList=[1,[4,[6]]] (calls: next, next, next)
init: stack = reverse([1,[4,[6]]]) = [[4,[6]], 1] (top on right) hasNext: top=1 is integer -> True | next: pop 1 -> return 1, stack=[[4,[6]]] hasNext: top=[4,[6]] is list -> pop, push reverse -> stack=[[6], 4]; top=4 integer -> True next: pop 4 -> return 4, stack=[[6]] hasNext: top=[6] is list -> pop, push reverse -> stack=[6]; top=6 integer -> True next: pop 6 -> return 6, stack=[] returned sequence: 1, 4, 6
What must stay true
The stack holds remaining elements to process. Pushing in reverse keeps the first element on top. Unpacking lists on demand gives lazy evaluation without pre-flattening.
Shape of the loop
init: stack = reverse(nestedList)
hasNext():
while stack and top(stack) is a list:
pop the list, push its items in reverse
return stack not empty
next(): hasNext(); return pop(stack).getInteger()Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Not pushing in reverse — if you push [1,[2,3]] in order, the list [2,3] would be on top instead of 1.