Flatten Nested List Iterator — Lazy Stack Design (LeetCode 341)

Flatten Nested List Iterator (LeetCode 341) is a design problem that combines stacks with the iterator pattern. The key insight is lazy flattening — you only expand nested lists when you actually need the next element.

The Problem

You are given a nested list of integers. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Input:  [[1,1], 2, [1,1]]
Output: [1, 1, 2, 1, 1]   (iteration order)

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

The NestedInteger interface provides:

• isInteger() — returns True if this holds a single integer
• getInteger() — returns the integer (if isInteger is True)
• getList() — returns the nested list (if isInteger is False)

Approach 1: Eager Flattening (Simple but Not Ideal)

class NestedIterator:
    """Flatten everything upfront — O(n) init, O(1) next."""

    def __init__(self, nestedList):
        self.flat = []
        self._flatten(nestedList)
        self.index = 0

    def _flatten(self, nested_list):
        for item in nested_list:
            if item.isInteger():
                self.flat.append(item.getInteger())
            else:
                self._flatten(item.getList())

    def next(self):
        val = self.flat[self.index]
        self.index += 1
        return val

    def hasNext(self):
        return self.index < len(self.flat)

This works but defeats the purpose of an iterator — we process everything upfront even if the caller only needs a few elements.

Approach 2: Lazy Stack Flattening (Preferred)

The stack-based approach only flattens as needed:

1. Push all items onto the stack in reverse order (so the first item is on top)
2. In hasNext(), keep flattening the top element until it is an integer (or the stack is empty)
3. In next(), pop and return the top integer

class NestedIterator:
    """
    Lazy flattening with a stack.
    Time: O(1) amortized for next(), O(L/N) amortized for hasNext()
          where L = total nested elements, N = total integers.
    Space: O(D) where D = maximum nesting depth.
    """

    def __init__(self, nestedList):
        # Push in reverse so first element is on top
        self.stack = list(reversed(nestedList))

    def next(self):
        # hasNext() guarantees top is an integer
        return self.stack.pop().getInteger()

    def hasNext(self):
        # Flatten until top of stack is an integer
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True
            # Top is a list — expand it
            self.stack.pop()
            children = top.getList()
            # Push children in reverse order
            for child in reversed(children):
                self.stack.append(child)
        return False

Why Reverse Order?

When you have [A, B, C] and push onto a stack, you want A on top. If you push in order A, B, C, then C is on top. So you push in reverse: C, B, A — now A is on top and will be processed first.

nestedList = [[1,1], 2, [1,1]]

Push reversed: stack = [[1,1], 2, [1,1]]
                        bottom ----------> top
                        [1,1]    2    [1,1]
Wait, reversed means:  [1,1] is pushed first, then 2, then [1,1]
Stack top = [1,1] (the FIRST element of the original list) ✓

Step-by-Step Trace

Trace for [[1,1], 2, [1,1]]:

Init: stack = [[1,1], 2, [1,1]]  (reversed push)
      stack top → [1,1] (first element)

hasNext():
  top = [1,1] → is list, pop and push reversed children
  stack = [  [1,1], 2, 1, 1 ]
              bottom -------> top
  top = 1 → is integer → return True

next():  pop 1, return 1

hasNext():
  top = 1 → is integer → return True

next():  pop 1, return 1

hasNext():
  top = 2 → is integer → return True

next():  pop 2, return 2

hasNext():
  top = [1,1] → is list, pop and push reversed children
  stack = [ 1, 1 ]
  top = 1 → is integer → return True

next():  pop 1, return 1

hasNext():
  top = 1 → is integer → return True

next():  pop 1, return 1

hasNext():
  stack empty → return False

Output: 1, 1, 2, 1, 1 ✓

Handling Empty Nested Lists

What about [[], [[]], 1]? There are empty lists that produce no integers.

Init: stack = [1, [[]], []]  (reversed)

hasNext():
  top = [] → is list, pop, getList() = [], push nothing
  stack = [1, [[]]]
  top = [[]] → is list, pop, push reversed children = [[]]
  Hmm wait — getList() returns [[]], which is a list containing one empty list.
  Push reversed: stack = [1, []]
  top = [] → is list, pop, push nothing
  stack = [1]
  top = 1 → is integer → return True

next(): return 1

The hasNext() loop naturally handles any depth of empty nesting.

Complexity Analysis

Operation	Time (amortized)	Space
__init__	O(k) where k = top-level items	O(k)
hasNext	O(1) amortized	O(D) depth
next	O(1)	O(1)

Why amortized O(1)? Each NestedInteger is pushed and popped at most once across all calls. Total work across all hasNext() calls = O(total elements).

Edge Cases

1. Flat list — [1, 2, 3] → no flattening needed
2. Deeply nested — [[[[[1]]]]] → multiple expansions before reaching integer
3. Empty lists — [[], 1, []] → skips empty lists, returns 1
4. All empty — [[], [[]], []] → hasNext() returns False immediately
5. Single integer — [5] → one next() call

Eager vs Lazy Comparison

Aspect	Eager	Lazy (Stack)
Init time	O(n) flatten all	O(k) top-level only
next()	O(1)	O(1) amortized
Memory	O(n) store all ints	O(D) stack depth
Early stop	Wasted work	Efficient
Implementation	Simpler	Slightly complex

Choose lazy when the caller might stop early or when the list is very large. Choose eager when you know every element will be consumed and simplicity matters.

When to Use This Pattern

The lazy-stack iterator pattern is useful when:

• You need to lazily traverse a tree-like or nested structure
• The problem asks for an iterator interface (hasNext/next)
• Flattening everything upfront is too expensive or wasteful
• You want to process a deeply nested structure level by level

Related Problems

Problem	Difficulty	Key Idea
LeetCode 341 — Flatten Nested List Iterator	Medium	This problem
LeetCode 173 — BST Iterator	Medium	Lazy stack for in-order
LeetCode 385 — Mini Parser	Medium	Parse nested structure
LeetCode 565 — Array Nesting	Medium	Traversal pattern

Key Takeaway

The Flatten Nested List Iterator teaches a core design principle: use a stack for lazy depth-first traversal. By pushing children in reverse order and flattening only the top of the stack in hasNext(), you get an elegant iterator that handles arbitrary nesting depth with minimal memory.