2625. Flatten Deeply Nested Array


Problem Description

Given a multi-dimensional array arr and a depth n, we are tasked to create a flattened version of arr. A multi-dimensional array contains integers or more multi-dimensional arrays, just like folders that can contain files or more folders. Our goal is to simplify this structure by converting it into a one-dimensional array. The flattening should only occur up to the depth n. So, if the depth of an element is less than n, we will not flatten that part of the array any further. The depth of the elements in the first array is considered to be 0.

Intuition

The problem begs for a recursive approach as we are dealing with a structure that is defined in terms of itselfā€”arrays within arrays. The recursion strategy should consider two things each time it is called: the array we are currently working on, and how deep we are, indicated by n.

Here's our basic strategy:

  • If n is 0 or less, we don't do any flattening and return the array as it is. This serves as our base case for the recursion because if we've reached the depth limit, no further flattening should be done.
  • We create an empty array to store the flattened elements, ans.
  • We then iterate over the elements of arr. For each element:
    • If it's an array itself, we call the flat function recursively on this array, decreasing n by 1. This step gradually works through nested arrays and peels away layers as determined by the depth n.
    • If it's not an array (i.e., an integer), we add it directly to ans.
  • Finally, we return ans, which holds the flattened structure up to the n-th depth level.

We avoid using the built-in Array.flat method, as the problem specification requires us to manually implement the flattening logic.

Solution Approach

The solution uses a recursive function to tackle the problem of flattening a multi-dimensional array to a specific depth (n). The algorithm is as follows:

  1. Base Case:
  • Check if n is less than or equal to 0. If this is the case, return the array as-is. This is because we've either reached the desired depth of flattening or don't want to flatten the array at all. The base case prevents further recursion.
  1. Initialization:
  • Initialize an empty array named ans. This will hold the partially flattened elements as we process the input array.
  1. Iteration:
  • Iterate through each element x of the array arr using a for loop.
  1. Recursion and Concatenation:
  • For each element x, check if it's an array using Array.isArray(x).
  • If x is an array, we need to dive deeper into its content:
    • Recursively call flat on element x, passing along the decremented depth n - 1. This recursive call will return x flattened up to n - 1 layers.
    • Use the spread operator (...) to concatenate the elements returned by the recursive call to the ans array. This flattens x one layer and merges its contents into ans.
  • If x is not an array, simply push x onto ans.
  1. Return Value:
  • After iterating through all elements, return the ans array. The ans array represents our multi-dimensional array flattened up to depth n.

The solution uses the concept of recursion, coupled with array operations such as iteration and concatenation. The spread operator is particularly useful to merge arrays without introducing additional nesting. This code elegantly avoids the complications of iterative approaches that would require stacks or complex loop control and instead relies on the execution stack from the recursive calls to manage the progression through different array levels.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's go through an example to illustrate the solution approach. Assume we are given the following multi-dimensional array arr and depth n:

arr = [[1, 2], [3, [4, 5]], 6]
n = 1

We want to flatten arr but only up to depth 1. Here's how the solution would work:

  1. Base Case: Our function would first check if n <= 0. In this case, n is 1, so we proceed with flattening.

  2. Initialization: We initialize an empty array ans. This will hold the partially flattened elements.

  3. Iteration:

    • We begin by iterating through arr. The first element is [1, 2], which is an array.
  4. Recursion and Concatenation:

    • Since the first element [1, 2] is an array, we recursively call flat([1, 2], n - 1), which decrements n by 1.
    • The recursive call will return the array [1, 2] because n now becomes 0, which hits our base case. This array gets concatenated to ans, resulting in ans = [1, 2].
    • The next element in arr is [3, [4, 5]], which is another array.
    • We recursively call flat([3, [4, 5]], n - 1).
    • This time, since the first element, 3, is not an array, it gets added to a new intermediate array. However, the second element [4, 5] is an array. Because our depth n at this point is 0 (since we decremented before), we add [4, 5] as it is without flattening it further. The intermediate result for this recursive call is [3, [4, 5]].
    • This intermediate result is then concatenated to ans, which now becomes ans = [1, 2, 3, [4, 5]].
    • The last element in arr is 6. It is not an array, so we directly add 6 to ans, resulting in ans = [1, 2, 3, [4, 5], 6].
  5. Return Value: We have finished iterating through arr, and we return ans. The final result is a flattened array up to depth 1:

[1, 2, 3, [4, 5], 6]

As you can see, the algorithm carefully flattens each layer of the array only up to the specified depth n and retains the nested structure beyond that depth. The use of recursion allows us to naturally handle arrays of varying depths without the need for complex loop control or extra data structures.

Solution Implementation

1# Import the typing module for type definitions
2from typing import Union, List
3
4# Define a MultiDimensionalArray where an element can be either an integer or another MultiDimensionalArray
5MultiDimensionalArray = List[Union[int, 'MultiDimensionalArray']]
6
7def flat(array: MultiDimensionalArray, depth: int) -> MultiDimensionalArray:
8    """
9    Flatten a multidimensional array 'array' up to a specific 'depth'.
10    If the depth is less than or equal to 0, the array is returned as is.
11  
12    Parameters:
13    array (MultiDimensionalArray): The multi-dimensional array to flatten.
14    depth (int): The depth indicating how many levels of nesting to flatten.
15
16    Returns:
17    MultiDimensionalArray: The flattened array up to the specified depth.
18    """
19
20    # Base case: if the depth is less than or equal to 0, return the array as is.
21    if depth <= 0:
22        return array
23  
24    # Initialize an empty list to store the flattened result
25    flattened_array = []
26  
27    # Iterate over each element in the input array
28    for element in array:
29        # Check if the element is a list (array) itself
30        if isinstance(element, list):
31            # If it is a list, recursively flatten it with a decremented depth, and extend the result to the flattened array
32            flattened_array.extend(flat(element, depth - 1))
33        else:
34            # If the element is an integer, append it to the flattened array
35            flattened_array.append(element)
36  
37    # Return the result
38    return flattened_array
39
1import java.util.ArrayList;
2import java.util.List;
3
4// Define the type for a MultiDimensionalArray where each element can either be an Integer or another MultiDimensionalArray.
5class MultiDimensionalArray extends ArrayList<Object> {}
6
7public class FlattenArray {
8
9    // Define the 'flat' function that takes a MultiDimensionalArray 'array' and 
10    // a depth 'depth' indicating how many levels of nesting to flatten.
11    public static MultiDimensionalArray flat(MultiDimensionalArray array, int depth) {
12        // If the specified depth is less than or equal to 0, return the array as is.
13        if (depth <= 0) {
14            return array;
15        }
16      
17        // Initialize an empty array to store the flattened result.
18        MultiDimensionalArray flattenedArray = new MultiDimensionalArray();
19      
20        // Iterate over each element in the input array.
21        for (Object element : array) {
22            // Check if the element is an array itself.
23            if (element instanceof MultiDimensionalArray) {
24                // If it is, recursively flatten the array element with reduced depth and append the result.
25                flattenedArray.addAll(flat((MultiDimensionalArray) element, depth - 1));
26            } else {
27                // If it's not an array, append the element as is to the flattened result.
28                flattenedArray.add(element);
29            }
30        }
31      
32        // Return the flattened array.
33        return flattenedArray;
34    }
35
36    // Main method to test the 'flat' function.
37    public static void main(String[] args) {
38        // Example usage:
39        MultiDimensionalArray nestedArray = new MultiDimensionalArray();
40        nestedArray.add(1);
41        nestedArray.add(new MultiDimensionalArray() {{
42            add(2);
43            add(new MultiDimensionalArray() {{
44                add(3);
45                add(4);
46            }});
47        }});
48        nestedArray.add(5);
49      
50        // Specify the depth to which the array should be flattened.
51        int depth = 1;
52      
53        // Flatten the array and print the result.
54        MultiDimensionalArray result = flat(nestedArray, depth);
55        System.out.println(result);
56    }
57}
58
1#include <vector>
2#include <variant>
3#include <type_traits>
4
5// Define the variant type for an Element which can either be an integer or a pointer to a MultiDimensionalArray.
6using Element = std::variant<int, std::vector<int>*>;
7
8// Define the type for a MultiDimensionalArray where each element can either be an integer or another MultiDimensionalArray pointer.
9using MultiDimensionalArray = std::vector<Element>;
10
11// Define the 'Flat' function that takes a MultiDimensionalArray reference 'array'
12// and an integer 'depth' indicating how many levels of nesting to flatten.
13MultiDimensionalArray Flat(const MultiDimensionalArray& array, int depth) {
14    // If the specified depth is less than or equal to 0, return the array as is.
15    if (depth <= 0) {
16        return array;
17    }
18  
19    // Initialize an empty array to store the flattened result.
20    MultiDimensionalArray flattenedArray;
21  
22    // Iterate over each element in the input array.
23    for (const Element& element : array) {
24        // Check if the element is an integer or another MultiDimensionalArray.
25        if (std::holds_alternative<int>(element)) {
26            // If it's an integer, append the element as is to the flattened array.
27            flattenedArray.push_back(element);
28        } else {
29            // If it's an array, recursively flatten the nested array element with reduced depth.
30            const MultiDimensionalArray& nestedArray = *std::get<std::vector<int>*>(element);
31            MultiDimensionalArray flattenedNestedArray = Flat(nestedArray, depth - 1);
32            // Append the result to the flattened array.
33            flattenedArray.insert(flattenedArray.end(), flattenedNestedArray.begin(), flattenedNestedArray.end());
34        }
35    }
36  
37    // Return the flattened result.
38    return flattenedArray;
39}
40
1// Define the type for a MultiDimensionalArray where each element can either be a number or another MultiDimensionalArray.
2type MultiDimensionalArray = (number | MultiDimensionalArray)[];
3
4// Define the 'flat' function that takes a MultiDimensionalArray 'array' and 
5// a depth 'depth' indicating how many levels of nesting to flatten.
6var flat = function (array: MultiDimensionalArray, depth: number): MultiDimensionalArray {
7    // If the specified depth is less than or equal to 0, return the array as is.
8    if (depth <= 0) {
9        return array;
10    }
11  
12    // Initialize an empty array to store the flattened result.
13    const flattenedArray: MultiDimensionalArray = [];
14  
15    // Iterate over each element in the input array.
16    for (const element of array) {
17        // Check if the element is an array itself.
18        if (Array.isArray(element)) {
19            // If it is, recursively flatten the array element with reduced depth and append the result.
20            flattenedArray.push(...flat(element, depth - 1));
21        } else {
22            // If it's not an array, append the element as is to the flattened result.
23            flattenedArray.push(element);
24        }
25    }
26  
27    // Return the flattened array.
28    return flattenedArray;
29};
30

Time and Space Complexity

Time Complexity

The time complexity of the flat function depends on the size and depth of the input array and the value of n. In essence:

  • Every element in the original array arr will be visited at least once.
  • If an element in the array is itself an array, the function will recursively visit each element of that subarray, decrementing n by 1 each time.
  • This process is repeated until n is reduced to 0 or there are no more nested arrays to flatten at the current level of depth.

To represent this formally, let's assume that the size of the array is m and the maximum depth of nested arrays is d. The function could theoretically traverse every element at every depth up to n times (where n ā‰¤ d), leading to a worst-case time complexity of O(m * d) when n >= d. However, the function only flattens n levels deep, so the time complexity is strictly bounded by n as well, thus it's O(m * min(d, n)).

Space Complexity

  • There is a space cost incurred every time the flat function is recursively called, which contributes to the space complexity. Each recursive call creates a new ans array. Given that the maximum depth of recursion is n, the space complexity due to recursive calls is O(n).
  • Additionally, we also need to consider the space required to store the ans array. In the worst case, this could be as large as the total number of elements in the flattened array, which depends on how many elements are at each level of depth and can vary widely.

The total space complexity considering both factors is O(n + m'), where m' is the total number of individual number elements encountered during the flattening operation up to n levels deep.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More