MediumNeetCode150StackDesignIterator
Flatten Nested List Iterator
Design an iterator to flatten a nested list of integers. The nestedList is either an integer or a list whose elements may also be integers or other lists.
Examples
Input
NestedIterator([[1,1],2,[1,1]])
Output
[1,1,2,1,1]
Flattened nested list.
Constraints
- •
1 <= nestedList.length <= 500 - •
The values of the integers in the nested list is in the range [-10^6, 10^6]
Approaches
Flatten the entire list on initialization.
CodeT: O(n) init, O(1) next/hasNext | S: O(n) flattened list
class NestedIterator:
def __init__(self, nestedList):
self.flat=[]; self.idx=0
def dfs(lst):
for item in lst:
if item.isInteger(): self.flat.append(item.getInteger())
else: dfs(item.getList())
dfs(nestedList)
def next(self): r=self.flat[self.idx]; self.idx+=1; return r
def hasNext(self): return self.idx<len(self.flat)Use stack to process nested lists lazily.
CodeT: O(n) worst, O(1) amortized next | S: O(n) stack
class NestedIterator:
def __init__(self, nestedList):
self.stack=list(reversed(nestedList))
def next(self):
self.hasNext()
return self.stack.pop().getInteger()
def hasNext(self):
while self.stack:
top=self.stack[-1]
if top.isInteger(): return True
self.stack.pop()
for item in reversed(top.getList()): self.stack.append(item)
return FalseSame approach with lazy evaluation.
CodeT: O(1) amortized | S: O(n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Flatten First | O(n) init, O(1) next/hasNext | O(n) flattened list | Flatten the entire list on initialization. |
| Stack-Based | O(n) worst, O(1) amortized next | O(n) stack | Use stack to process nested lists lazily. |
| Stack Optimized | O(1) amortized | O(n) | Same approach with lazy evaluation. |
Flatten First
T: O(n) init, O(1) next/hasNextS: O(n) flattened list
Flatten the entire list on initialization.
Stack-Based
T: O(n) worst, O(1) amortized nextS: O(n) stack
Use stack to process nested lists lazily.
Stack Optimized
T: O(1) amortizedS: O(n)
Same approach with lazy evaluation.
Common Mistakes
Not handling nested depth correctly
Using wrong stack order
Not checking hasNext before next