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].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.
Java
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.
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. |
Flatten Nested List Iterator | Live Coding with Explanation | Leetcode - 341 • Algorithms Made Easy • 13,433 views views
Watch 9 more video solutions →Practice Flatten Nested List Iterator with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor