Watch 5 video solutions for Nested Array Generator, a medium level problem. This walkthrough by NeetCodeIO has 7,642 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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?
Problem Overview: You receive a nested array that may contain integers or other arrays. The task is to build a generator that yields every integer in order, effectively flattening the structure without building a new array in memory.
The challenge is handling arbitrary nesting depth while preserving order. Instead of pre-flattening the structure, the generator should lazily produce values as iteration continues. This pattern is common when working with recursive data structures or tree-like traversal.
Approach 1: Recursive Inorder Traversal (O(n) time, O(d) space)
The most natural solution treats the nested array like a tree. Each array represents a node whose children may be integers or further arrays. Traverse it using recursion. When you encounter an integer, yield it immediately. When you encounter another array, recursively iterate through it using yield* (JavaScript) or nested generator calls. The traversal behaves like a depth-first search where elements are emitted in order. Time complexity is O(n) because every element is visited once, and space complexity is O(d), where d is the maximum nesting depth due to the recursion stack. This approach is clean and concise, especially if you're comfortable with recursion and generator delegation.
Approach 2: Iterative Inorder Traversal Using Stack (O(n) time, O(d) space)
The iterative version removes recursion by maintaining your own stack. Start by pushing the initial array elements onto the stack in reverse order so the leftmost element is processed first. While the stack is not empty, pop the top element. If it is an integer, yield it. If it is another array, push its elements onto the stack again in reverse order. This simulates the same depth-first traversal but avoids function call overhead. Time complexity remains O(n) because each value is processed once. Space complexity is O(d) in the average case for nested depth, though the stack may temporarily hold more elements depending on structure. This pattern is common in problems involving stack-based traversal or iterative depth-first search.
Recommended for interviews: The recursive generator is usually the fastest way to express the idea and demonstrates strong understanding of recursion and lazy iteration. However, interviewers often ask for the iterative stack version as a follow-up to test whether you understand how recursion works internally. Showing both approaches demonstrates solid mastery of traversal patterns.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Inorder Traversal | O(n) | O(d) | Best for clean generator-based solutions when recursion depth is manageable |
| Iterative Traversal Using Stack | O(n) | O(d) | Preferred when avoiding recursion or when implementing DFS explicitly |