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 list nestedList.int next() Returns the next integer in the nested list.boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.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[-106, 106].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.
This approach utilizes recursion to flatten the nested list. The idea is to traverse each element in the nested list. If the element is an integer, it gets added to a result list. If it's a list, the function calls itself recursively to add its flattened elements to the result list.
The constructor initializes the object with a flattened list and an iterator index. The `flatten` method is a helper function that recursively adds elements to `flatList`. The `next` method returns the next element from `flatList`, while `hasNext` checks the bounds.
Time Complexity: O(N), where N is the total number of integers in the nested list. Space Complexity: O(N) for the flattened list storage.
This approach uses a stack to iterate over the nested list in a depth-first manner. This helps simulate recursive behavior iteratively, thus allowing the use of iterator pattern directly without full pre-flattening.
The implementation utilizes a stack to simulate recursive traversal. The stack is populated in reverse order to ensure elements are visited in correct sequence. The `hasNext` method ensures the top of the stack is an integer before processing.
JavaScript
C#
Time Complexity: Amortized O(1) per call for `next` and `hasNext` due to efficient stack management. Space Complexity: O(N), where N is the total number of integers stored in the stack during traversal.
| Approach | Complexity |
|---|---|
| Approach 1: Recursive Flattening | Time Complexity: O(N), where N is the total number of integers in the nested list. Space Complexity: O(N) for the flattened list storage. |
| Approach 2: Using Stack for Iterative Flattening | Time Complexity: Amortized O(1) per call for `next` and `hasNext` due to efficient stack management. Space Complexity: O(N), where N is the total number of integers stored in the stack during traversal. |
| 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. |
Flatten Nested List Iterator - Leetcode 341 - Python • NeetCodeIO • 16,142 views views
Watch 9 more video solutions →Practice Flatten Nested List Iterator with our built-in code editor and test cases.
Practice on FleetCode