Skip to content

2649. Nested Array Generator

Description

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 <= 105
  • 0 <= arr.flat()[i]Β <= 105
  • maxNestingDepth <= 105

Β 

Can you solve this without creating a new flattened version of the array?

Solutions

Solution 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
type MultidimensionalArray = (MultidimensionalArray | number)[];

function* inorderTraversal(arr: MultidimensionalArray): Generator<number, void, unknown> {
    for (const e of arr) {
        if (Array.isArray(e)) {
            yield* inorderTraversal(e);
        } else {
            yield e;
        }
    }
}

/**
 * const gen = inorderTraversal([1, [2, 3]]);
 * gen.next().value; // 1
 * gen.next().value; // 2
 * gen.next().value; // 3
 */

Comments