Flatten Nested List Iterator

How it works

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.

Steps

1. Constructor: Copy the nested list to a stack in reverse order (so the first element is on top).
2. next(): Pop the top element and return its integer value.
3. 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.

Complexity

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

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

Things to watch for

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.

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

class NestedIterator {
private:
    vector<NestedInteger> stack;

public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        stack = nestedList;
        reverse(stack.begin(), stack.end());
    }

    int next() {
        int val = stack.back().getInteger();
        stack.pop_back();
        return val;
    }

    bool hasNext() {
        while (!stack.empty()) {
            NestedInteger top = stack.back();
            if (top.isInteger()) {
                return true;
            }
            stack.pop_back();
            vector<NestedInteger> nestedList = top.getList();
            for (auto it = nestedList.rbegin(); it != nestedList.rend(); ++it) {
                stack.push_back(*it);
            }
        }
        return false;
    }
};