341. Flatten Nested List Iterator
Asked at Adobe, OpenAI, Walmart
Difficulty
Medium
Time
O(1) amortized per call
Space
O(n)
Pattern
Stack
Companies
3
Problem
You are given a nested list. Each element of the list is either an integer, or another list that itself may contain integers or more lists (any depth).
Design a class NestedIterator that walks through all the integers in this structure in left-to-right order, as if the nesting were removed. It must support two methods: next() returns the next integer, and hasNext() returns true if any integers are left, otherwise false.
You do not need to flatten everything at the start. The test harness just calls hasNext() and next() in a loop and collects the results, so a lazy design is fine. The goal is O(1) amortized time per call.
Nesting must be removed
Constraints
- ●
1 <= nestedList.length <= 500 - ●
The values of the integers in the nested list is in the range [-10^6, 10^6]
Examples
nestedList = [[1,1],2,[1,1]][1,1,2,1,1]nestedList = [1,[4,[6]]][1,4,6]Asked At
3 companies| Company | Difficulty | |
|---|---|---|
| Adobe | Medium | View all Adobe questions → |
| OpenAI | Medium | View all OpenAI questions → |
| Walmart | Medium | View all Walmart questions → |
How to Think About It
Stack-based approach: push all nested list items onto a stack in reverse order. When you encounter a list during popping, push its items (in reverse) onto the stack.
Why reverse order: a stack is LIFO. Pushing in reverse ensures the first element is on top for popping in the correct order.
Lazy evaluation: instead of flattening everything upfront, flatten on demand. When next() is called, pop from the stack until you find an integer. Push any nested lists you encounter along the way.
Edge cases: empty nested list, deeply nested lists, list containing only integers, list containing only empty lists.
Optimal Approach
Use a stack initialized with the nested list in reverse order.
next():
- While stack is not empty:
- Pop top element
- If it is an integer, return it
- If it is a list, push its elements in reverse order onto the stack
- Throw error (should not happen if hasNext is checked first)
hasNext():
- While stack is not empty and top is a list:
- Pop it and push its elements in reverse order
- Return stack is not empty
Time: next() is O(1) amortized (each element pushed and popped once). hasNext() is O(1) amortized. Space: O(n) where n is total number of integers.
Stack, pushed in reverse
What Trips People Up in Real Interviews
Pushing nested list elements in forward order instead of reverse. A stack is LIFO, so pushing in forward order reverses the output. Always push in reverse to maintain correct iteration order.
Flattening the entire nested list eagerly in the constructor. The problem requires O(1) amortized for next(), which means lazy flattening. Eager flattening uses O(n) time upfront and may be rejected by the interviewer.
Using recursion or DFS instead of a stack. Recursion works but uses O(d) call stack space where d is max depth. The stack-based approach avoids stack overflow on deeply nested lists.
Forgetting that hasNext() must also flatten lazily. If hasNext() does not advance the stack past nested lists, calling hasNext() multiple times without next() could give wrong results.
Not handling empty nested lists or empty sublists. An input like [[], [1], []] should still yield [1]. If your hasNext() or next() does not skip empty lists, you will return incorrect values.
Solution Code
O(1) amortized per call timeclass NestedIterator:
def __init__(self, nestedList):
self.stack = list(reversed(nestedList))
def next(self):
while self.stack:
top = self.stack.pop()
if isinstance(top, int):
return top
self.stack.extend(reversed(top))
return -1
def hasNext(self):
while self.stack:
if isinstance(self.stack[-1], int):
return True
self.stack.extend(reversed(self.stack.pop()))
return FalseFrequently Asked Questions
What is the Flatten Nested List Iterator problem?
You are given a nested list of integers NestedInteger. Implement an iterator to flatten it. Each element is either an integer or a list whose elements may also be integers or other lists. The iterator should support next() and hasNext() in `O(1)` amortized time.
How do you solve Flatten Nested List Iterator?
The optimal approach runs in O(1) amortized per call time and O(n) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Flatten Nested List Iterator?
Flatten Nested List Iterator is asked at Adobe, OpenAI, Walmart. It is a medium difficulty problem.
What are common mistakes on Flatten Nested List Iterator?
- Pushing nested list elements in forward order instead of reverse. A `stack` is LIFO, so pushing in forward order reverses the output. Always push in reverse to maintain correct iteration order.
- Flattening the entire nested list eagerly in the constructor. The problem requires `O(1)` amortized for `next()`, which means lazy flattening. Eager flattening uses `O(n)` time upfront and may be rejected by the interviewer.
- Using recursion or DFS instead of a `stack`. Recursion works but uses `O(d)` call stack space where `d` is max depth. The `stack`-based approach avoids stack overflow on deeply nested lists.
- Forgetting that `hasNext()` must also flatten lazily. If `hasNext()` does not advance the `stack` past nested lists, calling `hasNext()` multiple times without `next()` could give wrong results.
- Not handling empty nested lists or empty sublists. An input like `[[], [1], []]` should still yield `[1]`. If your `hasNext()` or `next()` does not skip empty lists, you will return incorrect values.