⚡Flashcard Drill➔
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

  1. Use an explicit stack of the nested list, with the elements in reverse order so the next element is on top.
  2. hasNext normalises the stack: while the top is a list, pop it and push its elements in reverse.
  3. Once the top is an integer, hasNext is true and next simply pops it.
  4. 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 True from hasNext without normalising: the top might be a list, so next would 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.
🎯 Drill This Card Now➔

🧩 Related Stack Problems