Flatten Nested List Iterator - Video Solutions
Flatten Nested List Iterator - Leetcode 341 - Python
Flatten Nested List Iterator - Video Solution
Watch 10 video solutions for Flatten Nested List Iterator, a medium level problem involving Stack, Tree, Depth-First Search. This walkthrough by NeetCodeIO has 16,806 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.
Implement the NestedIterator class:
NestedIterator(List<NestedInteger> nestedList)Initializes the iterator with the nested listnestedList.int next()Returns the next integer in the nested list.boolean hasNext()Returnstrueif there are still some integers in the nested list andfalseotherwise.
Your code will be tested with the following pseudocode:
initialize iterator with nestedList
res = []
while iterator.hasNext()
append iterator.next() to the end of res
return res
If res matches the expected flattened list, then your code will be judged as correct.
Example 1:
Input: nestedList = [[1,1],2,[1,1]] Output: [1,1,2,1,1] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Input: nestedList = [1,[4,[6]]] Output: [1,4,6] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].
Constraints:
1 <= nestedList.length <= 500- The values of the integers in the nested list is in the range
[-106, 106].
Approach Overview
Problem Overview: You receive a list where each element is either an integer or another nested list. The task is to design an iterator that returns all integers in a flattened order. Calls to next() should return the next integer, and hasNext() should indicate whether more integers remain.
The challenge is not just flattening the list, but designing an iterator interface that efficiently processes nested structures. The structure behaves like a tree where lists are internal nodes and integers are leaf nodes. Traversing it requires techniques similar to Depth-First Search.
Approach 1: Recursive Flattening (O(n) time, O(n) space)
This approach performs a full depth-first traversal of the nested structure during initialization. Each element is inspected: if it is an integer, append it to a result list; if it is another list, recursively flatten it. After this preprocessing step, the iterator simply walks through the flattened array using an index pointer. next() returns the current element and increments the pointer, while hasNext() checks whether the pointer is still within bounds. The key idea is trading memory for simplicity by precomputing the entire flattened sequence. This solution uses recursion and mirrors standard DFS traversal patterns.
Approach 2: Using Stack for Iterative Flattening (O(n) time, O(d) space)
This approach avoids flattening everything upfront and instead processes the structure lazily using a stack. Push all elements of the nested list onto the stack in reverse order. During hasNext(), check the top element: if it is an integer, return true; if it is a list, pop it and push its contents back onto the stack in reverse order. This ensures the next element processed matches the correct traversal order. The stack simulates recursion and effectively performs an iterative DFS. Space usage depends on the maximum nesting depth d rather than the total number of integers.
This method aligns closely with how iterators are typically implemented in system design problems. Instead of storing all values, it maintains traversal state dynamically. The logic resembles how an iterator walks through a complex structure while exposing a simple interface.
Recommended for interviews: The stack-based iterator approach is usually preferred. Recursive flattening demonstrates understanding of DFS, but it eagerly stores all integers and uses extra memory. The stack solution keeps the iterator lazy and processes elements only when needed, which better matches real-world iterator design patterns.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Flattening | O(n) | O(n) | When simplicity matters and precomputing the entire flattened list is acceptable. |
| Stack-Based Iterative Iterator | O(n) | O(d) | Preferred for interviews and production-style iterator design with lazy evaluation. |