Flatten Nested List Iterator
Asked at Adobe, OpenAI, Walmart
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.
Asked At
| 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.
Visual walkthrough for [[1,1],2,[1,1]]:
Push in reverse: stack = [2, [1,1], [1,1]] (top at right).
Pop: [1,1] is a list. Push its items in reverse: stack = [2, [1,1], 1, 1].
Pop: 1. Return 1. Stack = [2, [1,1], 1].
Pop: 1. Return 1. Stack = [2, [1,1]].
Pop: [1,1] is a list. Push: stack = [2, 1, 1].
Pop: 1. Return 1. Stack = [2, 1].
Pop: 1. Return 1. Stack = [2].
Pop: 2. Return 2. Stack empty.
hasNext() returns false.
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.
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
class 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.