341. Flatten Nested List Iterator - Explanation

1. Recursion (Flatten And Store Into Global List)

Intuition

The nested list can contain integers or other nested lists at any depth. We can flatten the entire structure upfront using depth-first traversal. By storing all integers in a flat array during construction, subsequent next() and hasNext() calls become simple array operations.

Algorithm

Constructor: Initialize an empty array and a pointer at 0. Call dfs() on the nested list to populate the array.
dfs(nestedArr): For each element in the nested array:
- If it's an integer, append it to the array.
- If it's a list, recursively call dfs() on that list.
next(): Return the element at the current pointer and increment the pointer.
hasNext(): Return true if the pointer is less than the array length.

class NestedIterator:
    def __init__(self, nestedList):
        self.arr = []
        self.ptr = 0
        self.dfs(nestedList)

    def next(self):
        val = self.arr[self.ptr]
        self.ptr += 1
        return val

    def hasNext(self):
        return self.ptr < len(self.arr)

    def dfs(self, nestedArr):
        for num in nestedArr:
            if num.isInteger():
                self.arr.append(num.getInteger())
            else:
                self.dfs(num.getList())

Time & Space Complexity

Time complexity: $O(n + d)$
Space complexity: $O(n + d)$

Where $n$ is the number of integers and $d$ is the nesting depth.

2. Recursion (Flatten And Return)

Intuition

This is a variation of the first approach where the recursive function returns a flattened list instead of modifying a global variable. Each recursive call builds and returns its own list, which gets merged into the parent's result.

Algorithm

Constructor: Call dfs() on the nested list and store the returned array. Initialize pointer to 0.
dfs(nestedArr): Create an empty result list. For each element:
- If it's an integer, append it to the result.
- If it's a list, recursively call dfs() and extend the result with the returned list.
- Return the result.
next(): Return the element at the current pointer and increment it.
hasNext(): Return true if the pointer is less than the array length.

class NestedIterator:
    def __init__(self, nestedList):
        self.arr = self.dfs(nestedList)
        self.ptr = 0

    def dfs(self, nestedArr):
        res = []
        for num in nestedArr:
            if num.isInteger():
                res.append(num.getInteger())
            else:
                res.extend(self.dfs(num.getList()))
        return res

    def next(self):
        val = self.arr[self.ptr]
        self.ptr += 1
        return val

    def hasNext(self):
        return self.ptr < len(self.arr)

Time & Space Complexity

Time complexity: $O(n + d)$
Space complexity: $O(n + d)$

Where $n$ is the number of integers and $d$ is the nesting depth.

3. Recursion + Stack

Intuition

We can use recursion to flatten the list and store the integers in a stack. By reversing the stack after flattening, we can pop elements in the correct order. This combines recursive traversal with stack-based iteration.

Algorithm

Constructor: Initialize an empty stack. Call dfs() on the nested list, then reverse the stack.
dfs(nested): For each element:
- If it's an integer, push it onto the stack.
- If it's a list, recursively call dfs() on it.
next(): Pop and return the top element from the stack.
hasNext(): Return true if the stack is not empty.

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = []
        self.dfs(nestedList)
        self.stack.reverse()

    def next(self) -> int:
        return self.stack.pop()

    def hasNext(self) -> bool:
        return len(self.stack) > 0

    def dfs(self, nested):
        for num in nested:
            if num.isInteger():
                self.stack.append(num.getInteger())
            else:
                self.dfs(num.getList())

Time & Space Complexity

Time complexity: $O(n + d)$
Space complexity: $O(n + d)$

Where $n$ is the number of integers and $d$ is the nesting depth.

4. Stack

Intuition

Instead of flattening everything upfront, we can flatten lazily using a stack. We push the NestedInteger objects themselves onto the stack (in reverse order). When checking hasNext(), we unpack nested lists on demand until we find an integer at the top. This approach is more memory-efficient when we don't need to iterate through all elements.

Algorithm

Constructor: Copy the nested list to a stack in reverse order (so the first element is on top).
next(): Pop the top element and return its integer value.
hasNext(): While the stack is not empty:
- If the top element is an integer, return true.
- Otherwise, pop the nested list, reverse it, and push its elements back onto the stack.
- Return false if the stack becomes empty.

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = nestedList
        self.stack.reverse()

    def next(self) -> int:
        return self.stack.pop().getInteger()

    def hasNext(self) -> bool:
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True

            self.stack.pop()
            self.stack.extend(reversed(top.getList()))
        return False

Time & Space Complexity

Time complexity: $O(n + d)$
Space complexity: $O(n)$

Where $n$ is the number of integers and $d$ is the nesting depth.

Common Pitfalls

Calling next() Without Checking hasNext() First

The iterator contract requires calling hasNext() before next(). In lazy evaluation approaches, hasNext() is responsible for ensuring an integer is at the top of the stack. Calling next() without first calling hasNext() may return a nested list object instead of an integer, or cause an exception when the stack is empty.

Not Handling Empty Nested Lists

A nested list can contain empty lists like [[]] or [[], [1, []], 2]. Failing to handle these causes hasNext() to return true when no integers remain, or next() to fail. The lazy approach must continue unpacking until it finds an actual integer or the stack becomes empty.

Forgetting to Reverse When Pushing to Stack

When using a stack for lazy evaluation, elements must be pushed in reverse order so the first element ends up on top. Pushing in forward order reverses the iteration order. Similarly, when popping a nested list and pushing its contents, those contents must also be reversed to maintain correct order.