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 <= 105Can you solve this without creating a new flattened version of the array?
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.
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.
JavaScript
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.
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.
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.
JavaScript
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.
| Approach | Complexity |
|---|---|
| Recursive Inorder Traversal | Time Complexity: O(N), where N is the total number of integers in the arrays since we visit each element once. |
| Iterative Inorder Traversal Using Stack | Time Complexity: O(N), where N is the total number of integers in the arrays. |
This is the Most Asked FAANG Interview Question! - Two Sum - Leetcode 1 • Greg Hogg • 649,204 views views
Watch 9 more video solutions →Practice Nested Array Generator with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor