Flatten Nested List Iterator LeetCode 341

LeetCode 341 — Flatten Nested List Iterator — asks you to implement a NestedIterator class with next() and hasNext() methods. The input is a nested list where each element is either an integer or a list of integers (which can itself contain nested lists).

For example, [[1,1],2,[1,1]] should iterate as 1, 1, 2, 1, 1. The nesting can be arbitrary deep. The iterator must process elements lazily — it should not flatten the entire structure upfront if possible.

Two approaches exist: eager (DFS to flatten everything into a list during initialization) and lazy (use a stack to flatten on-demand during hasNext calls). The lazy approach is preferred because it handles large or infinite nested structures gracefully.

The simplest approach: during initialization, recursively flatten the entire nested list into a plain list of integers. Use a pointer to track the current position. next() returns the element at the pointer and advances it. hasNext() checks if the pointer is within bounds.

The DFS recursion is straightforward: for each element, if it is an integer, append it to the flat list. If it is a list, recursively flatten it. After initialization, next() and hasNext() are both O(1).

The downside: this approach processes the entire input upfront, using O(N) time and space during initialization where N is the total number of integers. If the nested list is very large or generated lazily, this defeats the purpose of an iterator.

Initialize a stack with the elements of the nested list pushed in reverse order (so the first element is on top). The stack holds NestedInteger objects — both integers and lists.

hasNext(): while the stack is non-empty, peek at the top. If it is an integer, return true. If it is a list, pop it, and push its children in reverse order onto the stack. This flattens one level of nesting. Repeat until the top is an integer or the stack is empty.

next(): call hasNext() to ensure the top is an integer (this is the standard iterator contract). Pop and return the integer. The flattening happens lazily — only when hasNext() is called, and only as deep as needed.

Consider nestedList = [[1,1],2,[1,1]]. Initialize stack (reversed): [[1,1], 2, [1,1]] → push [1,1] first, then 2, then [1,1]. Stack top-to-bottom: [1,1], 2, [1,1].

hasNext(): top is [1,1] (a list). Pop it, push its children reversed: push 1, then 1. Stack: 1, 1, 2, [1,1]. Top is 1 (integer) → return true. next(): pop 1, return 1. hasNext(): top is 1 → true. next(): pop 1, return 1.

hasNext(): top is 2 (integer) → true. next(): pop 2, return 2. hasNext(): top is [1,1] (list). Pop, push children: 1, 1. Stack: 1, 1. Top is 1 → true. next(): 1. hasNext(): top 1 → true. next(): 1. hasNext(): stack empty → false. Output: 1, 1, 2, 1, 1.

Python lazy: self.stack = list(reversed(nestedList)). def hasNext(): while self.stack: if self.stack[-1].isInteger(): return True. top = self.stack.pop(). self.stack.extend(reversed(top.getList())). return False. def next(): return self.stack.pop().getInteger().

Java lazy: use a Deque<NestedInteger> stack initialized with reversed input. hasNext() flattens with while loop. next() pops and returns getInteger(). Use addLast/removeLast for stack operations on ArrayDeque.

Python eager: self.flat = []. def dfs(nl): for item in nl: if item.isInteger(): self.flat.append(item.getInteger()). else: dfs(item.getList()). dfs(nestedList). self.idx = 0. next()/hasNext() use self.idx.

Lazy approach: amortized O(1) per next()/hasNext() call. Each NestedInteger is pushed onto and popped from the stack exactly once across all calls. Total work over N integers: O(N + L) where L is the total number of lists at all nesting levels.

Space: O(D + N) where D is the maximum nesting depth (stack depth during flattening) and N is the number of elements on the stack at any time. In the worst case (all elements at the deepest level), the stack holds O(N) elements.

Eager approach: O(N) initialization time, O(1) per next()/hasNext(). Space: O(N) for the flat list. Simpler but uses more upfront time and memory.

Peeking Iterator (LeetCode 284) wraps an existing iterator with a peek() method. It builds on the iterator concept from this problem but at a simpler level. Good warm-up before tackling nested list flattening.

Zigzag Iterator (LeetCode 281) alternates between two lists. Like Flatten Nested List Iterator, it manages multiple sources with a queue/stack. The pattern of "which source to read from next" is shared.

Design Compressed String Iterator (LeetCode 604) processes a run-length encoded string lazily. The lazy evaluation principle — decode only when needed — is identical to the lazy stack approach in this problem.