Flatten Nested List Iterator
mediumTime: O(n)Space: O(d)
Signals to notice
iterate through nested structure lazilyflatten on demandstack simulates recursion
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.
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.
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.