Meta — Flatten Nested List Iterator (Stack-Based Lazy Evaluation)

Problem Statement#

Given a nested list of integers where each element is either an integer or a list of integers (to any depth), implement an iterator that flattens it lazily.

Constraints:

• 1 <= nestedList.length <= 500
• Values are in range [-10^6, 10^6]
• Nesting can be arbitrarily deep

Input:  nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]

Input:  nestedList = [1,[4,[6]]]
Output: [1,4,6]

Why This Problem Matters#

The Flatten Nested List Iterator (LeetCode 341) is a Meta top-5 interview problem that tests your ability to design clean, lazily-evaluated data structures. Meta uses this to screen for engineers who understand iterator protocols, stack-based tree traversal, and encapsulation — skills directly applicable to React virtual DOM traversal and recursive data processing pipelines.

This problem is deceptively simple on the surface. A naive approach pre-flattens the entire list in __init__, which works but misses the point: a real iterator should be lazy, computing the next value only when requested. This distinction matters at scale when the nested list is enormous and you only need the first few elements.

Google and Amazon also test this variant under the guise of "design a file system iterator" or "lazy evaluation of tree nodes," making it a high-return problem to master thoroughly.

The Core Insight#

Push the entire nestedList onto a stack in reverse order. When hasNext() is called, peek at the top element. If it is an integer, return true. If it is a list, pop it, push its elements in reverse order, and repeat. This achieves true lazy evaluation — only the minimal work needed for the next integer is done.

The key invariant: after hasNext() returns true, the stack top is guaranteed to be an integer. next() simply pops and returns it. This separation of concerns is the design pattern Meta evaluates.

Visual Dry Run#

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

Solution (Optimal)#

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

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

Time: O(N) total across all calls — each element is pushed and popped exactly once Space: O(D + N) — D is max nesting depth, N is total elements

Common Mistakes#

• Pre-flattening everything in __init__ — technically correct but defeats lazy evaluation intent
• Forgetting to reverse when pushing a list's children onto the stack
• Not handling the empty list case in hasNext() (infinite loop risk)
• Calling next() without first calling hasNext() — undefined behavior
• Mutating the original nestedList instead of using a copy

Interview Tips#

• Lead with the lazy approach — Meta values design thinking over brute force
• Explain why hasNext() does the heavy lifting rather than next()
• Mention that the stack invariant (top is always int after hasNext() returns true) is the key
• Ask if multiple threads will call this iterator — leads to locking discussion
• Bring up the alternative: a generator function using yield from for Pythonic solutions

Follow-up Questions#

• What if the structure is infinite (lazily generated)? — Use generators instead of pre-collecting
• How would you implement this as a Python generator? — yield from recursion
• How do you handle concurrent access? — Mutex around stack operations
• Can you implement peek() efficiently? — Cache last hasNext() result
• What if lists can contain null? — Add null check before isInteger()

Key Takeaways#

• The stack stores elements in reverse order so the leftmost element sits on top, enabling O(1) access
• hasNext() must flatten lazily: keep popping lists and pushing their children until an integer is on top
• Total time complexity is O(N) amortized across all operations — each element is processed exactly once
• Meta tests this to evaluate understanding of iterator design patterns and lazy evaluation
• The clean interface (only next() and hasNext()) hides stack complexity — this is encapsulation by design
• Pre-flattening works for small inputs but fails on infinite or streaming nested structures
• This pattern generalizes to any recursive data structure: trees, JSON blobs, file system hierarchies