NeetCode #373LC-341MediumStack
← Back to All Problems#373 · #341 · Flatten Nested List Iterator(扁平化嵌套列表迭代器)
📌 Problem Statement & Constraints
This is an interactive problem. You are given a nested list of integers, where each element is either an integer or a list. Implement
NestedIterator with next() and hasNext(), flattening the structure. Constraints: the total number of integers is at most 10^4; the nesting depth is at most 1000.💡 Core Algorithmic Approaches
- Use an explicit stack of the nested list, with the elements in reverse order so the next element is on top.
hasNextnormalises the stack: while the top is a list, pop it and push its elements in reverse.- Once the top is an integer,
hasNextis true andnextsimply pops it. - Lazy flattening is important: eagerly expanding the whole structure would cost O(total size) up front and could blow the recursion depth.
💻 Benchmark Python3 Implementation
class NestedIterator:
def __init__(self, nestedList: ["NestedInteger"]):
# reversed so the first element ends up on top of the stack
self.st = list(reversed(nestedList))
def next(self) -> int:
return self.st.pop().getInteger()
def hasNext(self) -> bool:
while self.st:
top = self.st[-1]
if top.isInteger():
return True
self.st.pop()
# push the inner list reversed so its first element is on top
self.st.extend(reversed(top.getList()))
return False⚡ Complexity Deep Dive
⏱️ Time Complexity
O(1) amortised per operation: each element is pushed and popped once over the iterator's lifetime.
💾 Space Complexity
O(n) for the stack, where n is the total number of elements.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting to reverse when extending: without the reversal, the elements would be consumed in the wrong order.
- Eagerly flattening in the constructor: it works but costs O(n) up front and requires recursion or an explicit stack anyway.
- Returning
TruefromhasNextwithout normalising: the top might be a list, sonextwould fail. - Using recursion to flatten: the nesting depth can reach 1000, which risks exceeding the recursion limit.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.