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].The key challenge in Flatten Nested List Iterator is designing an iterator that returns integers from a deeply nested structure in a flat sequence. Instead of flattening the entire list upfront, an efficient approach uses a lazy traversal strategy.
A common technique is to use a stack to simulate depth-first search (DFS). Push elements of the nested list onto the stack in reverse order so the leftmost element is processed first. When the top element is a list, expand it by pushing its contents onto the stack. When it is an integer, it becomes the next value for the iterator.
This approach avoids precomputing the entire flattened array and processes elements only when needed. Each element is pushed and popped at most once, giving O(n) total time across all iterator operations and O(d) auxiliary space, where d represents the maximum nesting depth.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack-based DFS Iterator | O(n) total across all operations | O(d) where d is the maximum nesting depth |
| Pre-flatten using DFS | O(n) | O(n) |
Algorithms Made Easy
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.
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.
1public class NestedIterator implements Iterator<Integer> {
2 private List<Integer> flatList;
3 private int index;
4
5 public NestedIterator(List<NestedInteger> nestedList) {
6 flatList = new ArrayList<>();
7 index = 0;
8 flatten(nestedList);
9 }
10
11 private void flatten(List<NestedInteger> nestedList) {
12 for (NestedInteger element : nestedList) {
13 if (element.isInteger()) {
14 flatList.add(element.getInteger());
15 } else {
16 flatten(element.getList());
17 }
18 }
19 }
20
21 public Integer next() {
22 return flatList.get(index++);
23 }
24
25 public boolean hasNext() {
26 return index < flatList.size();
27 }
28}In Java, a similar recursive approach is employed. The `flatList` holds the flattened integers, and `index` tracks the iteration. The `hasNext` and `next` methods facilitate list traversal.
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.
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.
1class NestedIterator {
2 constructor(nestedList
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or variations of it are commonly asked in FAANG and other top tech company interviews. It tests design thinking, iterator implementation, and understanding of stacks and DFS traversal.
A stack is the most effective data structure for this problem. It allows you to process nested lists in depth-first order and dynamically expand lists while maintaining the correct traversal sequence.
The optimal approach uses a stack to simulate a depth-first traversal of the nested structure. Instead of flattening the list in advance, the iterator lazily expands nested lists only when needed, which keeps operations efficient and memory usage low.
Lazy flattening avoids storing all elements in a separate array at once, which can reduce memory usage. It also aligns with iterator design principles by computing the next value only when the user requests it.
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.