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.
1class NestedIterator:
2 def __init__(self, nestedList):
3 self.flatList = []
4 self.index = -1
5 self.flatten(nestedList)
6
7 def flatten(self, nestedList):
8 for element in nestedList:
9 if element.isInteger():
10 self.flatList.append(element.getInteger())
11 else:
12 self.flatten(element.getList())
13
14 def next(self):
15 self.index += 1
16 return self.flatList[self.index]
17
18 def hasNext(self):
19 return self.index + 1 < len(self.flatList)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.
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.
1public class NestedIterator {
2 private Stack<NestedInteger> stack = new Stack<NestedInteger>();
3
4 public NestedIterator(IList<NestedInteger> nestedList) {
5 Flatten(nestedList);
}
private void Flatten(IList<NestedInteger> nestedList) {
for (int i = nestedList.Count - 1; i >= 0; i--) {
stack.Push(nestedList[i]);
}
}
public bool HasNext() {
while (stack.Count > 0) {
NestedInteger top = stack.Pop();
if (top.IsInteger()) {
stack.Push(top);
return true;
}
Flatten(top.GetList());
}
return false;
}
public int Next() {
return stack.Pop().GetInteger();
}
}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.
Similar to the JavaScript solution, the C# code uses a stack to flatten the list iteratively. By pre-loading the stack in reverse order, we ensure correct traversal order. `HasNext` prepares the stack until the next integer is on top.