Flatten Nested List Iterator
mediumTime: O(n)Space: O(d)
Recognize the pattern
iterate through nested structure lazilyflatten on demandstack simulates recursion
Brute force idea
Flatten everything upfront into a list — O(n) space, wasteful if only a few elements are needed.
Better approach
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.
Key invariant
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.
Watch out for
Not pushing in reverse — if you push [1,[2,3]] in order, the list [2,3] would be on top instead of 1.