Given a multi-dimensional array of integers, return a generator object which yields integers in the same order as inorder traversal.
A multi-dimensional array is a recursive data structure that contains both integers and other multi-dimensional arrays.
inorder traversal iterates over each array from left to right, yielding any integers it encounters or applying inorder traversal to any arrays it encounters.
Example 1:
Input: arr = [[[6]],[1,3],[]] Output: [6,1,3] Explanation: const generator = inorderTraversal(arr); generator.next().value; // 6 generator.next().value; // 1 generator.next().value; // 3 generator.next().done; // true
Example 2:
Input: arr = [] Output: [] Explanation: There are no integers so the generator doesn't yield anything.
Constraints:
0 <= arr.flat().length <= 1050 <= arr.flat()[i] <= 105maxNestingDepth <= 105In #2649 Nested Array Generator, the goal is to iterate through a deeply nested array and yield its integer elements one by one using a generator pattern. Instead of flattening the entire structure first, an efficient approach is to traverse the array lazily and produce values as they are encountered.
A common strategy is to use recursion with generators. When an element is an integer, yield it directly using yield. If the element is another array, recursively iterate through it and delegate yielding using yield*. This allows the generator to seamlessly handle multiple nesting levels without creating extra flattened arrays.
An alternative approach uses an explicit stack to simulate depth‑first traversal. This avoids recursion while still ensuring elements are processed in the correct order. Both approaches ensure that each element is visited only once, leading to efficient traversal of the nested structure.
The overall complexity depends on the number of elements in the structure, since each value is processed exactly once.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursive Generator Traversal | O(n) | O(d) where d is nesting depth |
| Iterative Stack-Based Traversal | O(n) | O(d) where d is nesting depth |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
Generator functions can pass control to another generator function with "yield*" syntax.
Generator functions can recursively yield control to themselves.
You don't need to worry about recursion depth for this problem.
The recursive approach leverages the call stack to manage the traversal of the multi-dimensional array. This approach requires defining a function that will be called recursively whenever an array is encountered.
When implementing this recursively, we check if the element is an integer; if so, we yield it. If it is an array, we recursively call the function on this array.
Time Complexity: O(N), where N is the total number of integers in the arrays since we visit each element once.
Space Complexity: O(D) in the worst case due to recursion, where D is the depth of the nested lists.
1def inorderTraversal(arr):
2 for item in arr:
3 if isinstance(item, int):
4 yield item
5 elif isinstance(item, list):
6 yield from inorderTraversal(item)
7
8# Usage example:
9arr = [[[6]], [1, 3], []]
10generator = inorderTraversal(arr)
11print(list(generator))The function inorderTraversal takes a multi-dimensional array arr and iterates over its elements. If an element is an integer, it's directly yielded. If it is a list, the function is called recursively on the sublist, using yield from to yield each item from the resulting generator.
This method uses a stack to keep track of the state of the array traversal. It mimics the behavior of the call stack in recursion but uses an explicit data structure. We push elements onto the stack in reverse order, and pop them to yield integers or explore more sub-arrays.
Time Complexity: O(N), where N is the total number of integers in the arrays.
Space Complexity: O(N) due to the use of the stack.
1def inorderTraversal(arr):
2 stack = arr
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems involving nested array traversal, iterators, and generators are common interview patterns. While the exact problem may vary, the underlying concept of flattening or lazily iterating nested structures is frequently discussed.
Recursion with generators is the most natural fit because nested arrays form a tree-like structure. Alternatively, a stack can be used to simulate depth-first traversal iteratively while maintaining the correct processing order.
The optimal approach is to use a recursive generator that traverses the nested array depth-first. By yielding integers directly and delegating nested arrays using generator delegation, you can produce values lazily without flattening the whole structure.
Generators allow lazy evaluation, meaning values are produced only when needed. This avoids creating a full flattened array in memory, which can be more efficient for very large or deeply nested inputs.
The inorderTraversal function initializes a stack with the reversed main array. We pop elements from the stack; if it's an integer, we yield it. If it is a list, its elements are pushed onto the stack in reverse order to maintain the original order while traversing.