Meta — Flatten Nested List Iterator (Stack-Based)

Problem (Meta Top-5)

Given a NestedInteger list where each element is either an integer or a list, implement a NestedIterator with next() and hasNext().

Key Insight — Stack for Lazy Flattening

Push the list in reverse order onto a stack. hasNext() peeks and flattens one level if needed. next() returns the top integer.

Solutions

Python

class NestedIterator:
    def __init__(self, nestedList):
        self.stack = nestedList[::-1]

    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(top.getList()[::-1])
        return False

JavaScript

class NestedIterator {
    constructor(nestedList) { this.stack = [...nestedList].reverse(); }
    hasNext() {
        while (this.stack.length) {
            if (this.stack[this.stack.length-1].isInteger()) return true;
            const top = this.stack.pop();
            this.stack.push(...[...top.getList()].reverse());
        }
        return false;
    }
    next() { return this.stack.pop().getInteger(); }
}

Java

import java.util.*;
public class NestedIterator implements Iterator<Integer> {
    Deque<NestedInteger> stack = new ArrayDeque<>();
    public NestedIterator(List<NestedInteger> nl) {
        for (int i=nl.size()-1;i>=0;i--) stack.push(nl.get(i));
    }
    public boolean hasNext() {
        while (!stack.isEmpty()) {
            if (stack.peek().isInteger()) return true;
            NestedInteger ni = stack.pop();
            List<NestedInteger> list = ni.getList();
            for (int i=list.size()-1;i>=0;i--) stack.push(list.get(i));
        }
        return false;
    }
    public Integer next() { return stack.pop().getInteger(); }
}

C++

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

C

/* C: pre-flatten to array of ints, return sequentially */