Flatten Nested List Iterator

medium stack dfs design

Problem

Implement an iterator over a nested list of integers. Each element is either an integer or a list of integers (which may itself be nested). Support next() and hasNext().

Input[[1,1],2,[1,1]]

Output[1, 1, 2, 1, 1]

Push items onto a stack in reverse so peeking yields the leftmost integer.

nested list (JSON)

class NestedIterator:
    def __init__(self, nestedList):
        self.stack = list(reversed(nestedList))
    def next(self):
        self._top()
        return self.stack.pop().getInteger()
    def hasNext(self):
        return self._top()
    def _top(self):
        while self.stack and not self.stack[-1].isInteger():
            top = self.stack.pop().getList()
            for item in reversed(top):
                self.stack.append(item)
        return bool(self.stack)

class NestedIterator {
  constructor(list) { this.stack = list.slice().reverse(); }
  hasNext() {
    while (this.stack.length && !this.stack[this.stack.length - 1].isInteger()) {
      const top = this.stack.pop().getList();
      for (let i = top.length - 1; i >= 0; i--) this.stack.push(top[i]);
    }
    return this.stack.length > 0;
  }
  next() { this.hasNext(); return this.stack.pop().getInteger(); }
}

public class NestedIterator implements Iterator<Integer> {
    private Deque<NestedInteger> stack = new ArrayDeque<>();
    public NestedIterator(List<NestedInteger> nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) stack.push(nestedList.get(i));
    }
    public boolean hasNext() {
        while (!stack.isEmpty() && !stack.peek().isInteger()) {
            List<NestedInteger> top = stack.pop().getList();
            for (int i = top.size() - 1; i >= 0; i--) stack.push(top.get(i));
        }
        return !stack.isEmpty();
    }
    public Integer next() { hasNext(); return stack.pop().getInteger(); }
}

class NestedIterator {
    stack<NestedInteger*> st;
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) st.push(&nestedList[i]);
    }
    bool hasNext() {
        while (!st.empty() && !st.top()->isInteger()) {
            auto &v = st.top()->getList(); st.pop();
            for (int i = v.size() - 1; i >= 0; i--) st.push(&v[i]);
        }
        return !st.empty();
    }
    int next() { hasNext(); int v = st.top()->getInteger(); st.pop(); return v; }
};

Explanation

We need an iterator over a deeply nested list that hands out integers left to right. The key idea is a stack that we expand lazily — we only unpack a sublist when we are actually about to look at it.

In the constructor we push the top-level items onto the stack in reverse, so the leftmost item ends up on top. The helper hasNext() (or _top()) then makes sure the top is a real integer: while the top is a list, it pops that list and re-pushes its children in reverse.

Pushing children in reverse is what preserves left-to-right order — after expansion the first child sits on top. next() simply calls the helper to expose the next integer, then pops and returns it.

Example: [[1,1],2,[1,1]]. We start with these reversed on the stack; the top [1,1] expands to two 1s, which we emit, then 2, then the last [1,1] expands and emits two more — output [1,1,2,1,1].

Because each element is unpacked at most once, the cost is amortized O(1) per returned integer.

Time: O(1) amortized per element Space: O(depth + width)