Flatten Nested List Iterator

LeetCode 341 • Medium • Design

Design an iterator to flatten a nested list of integers.
NestedInteger is either an int or a list of NestedInteger. Use a stack; ensure the top is always an integer before next.

nextO(1)amortized

hasNextO(1)amortized

SpaceO(d)nesting depth

Step0

stack: …

Ready

Press Play or Step.

Speed:

✎ Whiteboard

Size:3

⌨ Type It

Practice until you don't need to look. Green highlights are the nuances to burn into memory.

═══ FLATTEN NESTED LIST ITERATOR ═══

PATTERN ▸ stack of NestedInteger amortized O(1)

① INIT

stack = nestedList[::-1]

② HASNEXT

while stack and not stack[-1].isInteger():

top = stack.pop(); push reversed(top.getList())

③ NEXT

hasNext(); return stack.pop().getInteger()

Verify your solution: