2649. Nested Array Generator


Problem Description

The problem requires us to work with a multi-dimensional array structure. This is an array where each element can either be an integer or another array of similar structure (which again could contain integers or other arrays). Our objective is to create a generator function that traverses this nested array structure in an 'inorder' manner. In the context of this problem, 'inorder traversal' means sequentially iterating over each element in the array. If the element is an integer, it is yielded by the generator. If the element is a sub-array, the generator applies the same inorder traversal to it.

Intuition

The solution requires an understanding of recursive data structures and generator functions in TypeScript. The recursive nature of the problem suggests that a recursive function may be an elegant solution. The 'inorder traversal' hints at a depth-first search (DFS) approach where for any given array element, we explore as deep as possible along each branch before backing up, which is a typical recursive behavior.

So, the intuitive approach is to iterate over the array, check if the current element is a number or another array.

  • If it is a number, we use 'yield' to return this number and pause the function's execution, allowing the numbers to be enumerated one by one.
  • If it is another array, we apply recursion and 'yield*' to delegate to the recursive generator. The use of 'yield*' (yield delegation) is crucial because it allows the yielded values from the recursive call to come through directly to the caller. This maintains the proper sequence without needing to manage intermediate collections or states.

This recursive generator pattern allows us to elegantly handle the varying depths of nested arrays and maintain the inorder traversal logic without complicating the process of maintaining the current state during iteration.

Solution Approach

The solution employs a simple yet effective recursive generator function to perform the inorder traversal of a multi-dimensional array.

First, we outline the function signature:

1function* inorderTraversal(arr: MultidimensionalArray): Generator<number, void, unknown> {

We declare a TypeScript generator function inorderTraversal that accepts a parameter arr, which is of type MultidimensionalArray. This type is an alias for an array that can have elements that are either numbers or, recursively, MultidimensionalArray.

Next, we implement the core logic:

1for (const e of arr) {
2    if (Array.isArray(e)) {
3        yield* inorderTraversal(e);
4    } else {
5        yield e;
6    }
7}
  • The generator function enters a loop, iterating over each element e in the input array arr.
  • For each element, we check if e is an array using the Array.isArray(e) method. If this is true, it indicates that we have encountered a nested array, so we must traverse it as well, which is done recursively.
  • yield* is used to delegate to another generator function—this allows the values from the recursive call to be yielded back to the caller of the original generator.

By using yield and yield*, the elements are yielded one by one, maintaining the expected order of an inorder traversal.

This recursive pattern allows us to succinctly handle the structure irrespective of the depth or complexity of the nesting. It elegantly scales to any level of nested arrays, effectively flattening the structure in an iterative fashion in the order the arrays are laid out. There is no need for additional data structures or managing a stack explicitly as the call stack of the recursive function calls handles this.

The TypeScript type system ensures that the generator function yields only numbers, and any attempt to yield something else will result in compile-time type-checking errors, which helps maintain the correctness of the implementation.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

In a binary min heap, the maximum element can be found in:

Example Walkthrough

To illustrate the solution approach, let's use a small example of a nested array structure and walk through how the generator function inorderTraversal operates on it.

Suppose we have the following multi-dimensional array:

1const nestedArray = [1, [2, [3, 4], 5], 6, [7, 8]];

The inorderTraversal function will traverse this nested structure and yield each number sequentially. Here's how it works step-by-step:

  1. The function begins the first iteration of the top-level array.
  2. It encounters the number 1 and yields it.
  3. The next element is [2, [3, 4], 5], which is an array. The function calls itself recursively with this array.
  4. Inside this recursive call:
    • It yields 2.
    • Encounters another nested array [3, 4] and recurses again.
    • In the next level of recursion, it yields 3 and 4 sequentially.
    • Having finished with the nested array [3, 4], the function backtracks to the previous level and yields 5.
  5. The function continues with the top-level array and yields 6.
  6. Lastly, it encounters another array [7, 8]:
    • It yields 7.
    • Then it yields 8.

The final order of yielded numbers reflects an inorder traversal of the multi-dimensional array:

11, 2, 3, 4, 5, 6, 7, 8

By utilizing recursion, the function correctly and efficiently handles nested structures of any depth without the need for explicitly managing the state or maintaining a stack. The yield and yield* keywords allow for a clear and concise definition of how values are passed back during the traversal.

Solution Implementation

1# Definition for a multidimensional list where each element can either be an integer
2# or another multidimensional list of similar structure.
3MultidimensionalList = list["MultidimensionalList" | int]
4
5# Generator function to traverse a multidimensional list in order.
6# This function yields each integer element encountered during the traversal.
7def inorder_traversal(arr: MultidimensionalList):
8    # Iterate over each element of the list.
9    for element in arr:
10        if isinstance(element, list):
11            # If the current element is a list, recursively traverse it.
12            yield from inorder_traversal(element)
13        else:
14            # If the current element is an integer, yield it.
15            yield element
16
17# Usage example:
18# Create a generator instance with a multidimensional list.
19# generator = inorder_traversal([1, [2, 3]])
20# Retrieve numbers from the generator in order.
21# next(generator)  # Returns 1
22# next(generator)  # Returns 2
23# next(generator)  # Returns 3
24
1import java.util.ArrayList;
2import java.util.Iterator;
3import java.util.List;
4
5// A nested list that can contain either integers or another nested list of integers.
6class NestedInteger {
7    private Integer value;
8    private List<NestedInteger> list;
9
10    public NestedInteger(Integer value) {
11        this.value = value;
12    }
13
14    public NestedInteger(List<NestedInteger> list) {
15        this.list = list;
16    }
17
18    public boolean isInteger() {
19        return value != null;
20    }
21
22    public Integer getInteger() {
23        return value;
24    }
25
26    public List<NestedInteger> getList() {
27        return list;
28    }
29}
30
31// Iterator to traverse a nested list of integers in order, yielding each number.
32class InorderTraversal implements Iterator<Integer> {
33    private List<Integer> flattenedList;
34    private int currentPosition;
35
36    public InorderTraversal(List<NestedInteger> nestedList) {
37        flattenedList = new ArrayList<>();
38        flattenList(nestedList);
39        currentPosition = 0;
40    }
41
42    private void flattenList(List<NestedInteger> nestedList) {
43        for (NestedInteger ni : nestedList) {
44            // If the current element is an integer, add it to the flattened list.
45            if (ni.isInteger()) {
46                flattenedList.add(ni.getInteger());
47            } else {
48                // If the current element is a nested list, recursively traverse it.
49                flattenList(ni.getList());
50            }
51        }
52    }
53
54    @Override
55    public boolean hasNext() {
56        // Return true if there are more elements to iterate over.
57        return currentPosition < flattenedList.size();
58    }
59
60    @Override
61    public Integer next() {
62        // Return the next integer in the traversal, if one exists.
63        return flattenedList.get(currentPosition++);
64    }
65}
66
67// Usage example:
68/*
69NestedInteger nestedList1 = new NestedInteger(1);
70NestedInteger nestedList2 = new NestedInteger(Arrays.asList(new NestedInteger(2), new NestedInteger(3)));
71List<NestedInteger> nestedList = Arrays.asList(nestedList1, nestedList2);
72
73InorderTraversal traversal = new InorderTraversal(nestedList);
74while (traversal.hasNext()) {
75    System.out.println(traversal.next()); // Prints 1, then 2, then 3 in order.
76}
77*/
78
1#include <vector>
2#include <cstdlib>
3#include <iterator>
4#include <iostream>
5
6// Type definition for a nested array where each element can either be an integer
7// or another nested array with a similar structure.
8using MultidimensionalArray = std::vector<std::variant<int, std::vector<int>>>;
9
10// This is a generator function declared with the using syntax.
11// It's not supported as a language construct in C++, so we need to simulate it.
12// For simplicity, we'll use a recursive lambda function within another function.
13std::vector<int> inorderTraversal(MultidimensionalArray& arr) {
14  
15    // A lambda function that traverses the array, which captures a local vector by reference,
16    // where it would push back elements. In actual generator function, this would directly yield elements.
17    std::vector<int> result;
18    std::function<void(const MultidimensionalArray&)> traverse = [&](const MultidimensionalArray& sub_arr) {
19        for (const auto& element : sub_arr) {
20            if (std::holds_alternative<int>(element)) {
21                // If the current element is a number, add it to the result.
22                result.push_back(std::get<int>(element));
23            } else {
24                // If the current element is an array, recursively traverse it.
25                traverse(std::get<MultidimensionalArray>(element));
26            }
27        }
28    };
29  
30    // Start the traversal from the root array.
31    traverse(arr);
32  
33    // Return the complete result of the traversal.
34    return result;
35}
36
37// Usage example:
38int main() {
39    // Create a nested (multidimensional) array.
40    MultidimensionalArray arr = {1, MultidimensionalArray{2, 3}};
41
42    // Retrieve the inorder traversal of the array.
43    std::vector<int> traversalResult = inorderTraversal(arr);
44
45    // Print the numbers retrieved from the traversal.
46    for (int num : traversalResult) {
47        std::cout << num << std::endl;
48    }
49
50    return 0;
51}
52
1// Type definition for a nested array where each element can either be a number
2// or another nested array of similar structure.
3type MultidimensionalArray = (MultidimensionalArray | number)[];
4
5// Generator function to traverse a multidimensional array in order.
6// This function yields each number element encountered during the traversal.
7function* inorderTraversal(arr: MultidimensionalArray): Generator<number, void, unknown> {
8    // Iterate over each element of the array.
9    for (const element of arr) {
10        if (Array.isArray(element)) {
11            // If the current element is an array, recursively traverse it.
12            yield* inorderTraversal(element);
13        } else {
14            // If the current element is a number, yield it.
15            yield element;
16        }
17    }
18}
19
20// Usage example:
21// Create a generator instance with a multidimensional array.
22// const generator = inorderTraversal([1, [2, 3]]);
23// Retrieve numbers from the generator in order.
24// generator.next().value; // Returns 1.
25// generator.next().value; // Returns 2.
26// generator.next().value; // Returns 3.
27

Time and Space Complexity

The given TypeScript code performs an inorder traversal on a multidimensional (nested) array to yield all the numbers contained therein. A generator function is defined to achieve this, which allows the user to retrieve the numbers one by one.

Time Complexity

The time complexity of this function can be evaluated by considering that each element in the multidimensional array is visited exactly once. If there are N numbers within the nested arrays, regardless of their specific arrangement, each number will be yielded exactly once by the generator function.

While nested arrays necessitate recursive calls, this does not multiply the number of operations per element; rather, it dictates the depth of those recursion calls. Therefore, the time complexity of the function is O(N), where N is the total number of elements.

Space Complexity

The space complexity is determined by the maximum depth of recursion needed to reach the innermost array. In the worst-case scenario — that is, a deeply nested array where each array contains only one sub-array until the deepest level — the space complexity is O(D), where D is the depth of the nested arrays. This space is used by the call stack of the recursive function.

In a more general scenario with uneven distribution of elements, the space complexity will still be determined by the depth of the recursion required but would be less than the maximum depth of all the elements. Therefore, we can consider the space complexity to be O(D), with an understanding that D indicates the depth of the deepest nesting.

If we consider the generator state which also takes up memory, this could add a constant factor to the space complexity, but does not change the overall O(D) space complexity.


Fast Track Your Learning with Our Quick Skills Quiz:

Which data structure is used in a depth first search?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄