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
is0
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, decreasingn
by1
. This step gradually works through nested arrays and peels away layers as determined by the depthn
. - If it's not an array (i.e., an integer), we add it directly to
ans
.
- If it's an array itself, we call the
- Finally, we return
ans
, which holds the flattened structure up to then
-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:
- Base Case:
- Check if
n
is less than or equal to0
. 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.
- Initialization:
- Initialize an empty array named
ans
. This will hold the partially flattened elements as we process the input array.
- Iteration:
- Iterate through each element
x
of the arrayarr
using afor
loop.
- Recursion and Concatenation:
- For each element
x
, check if it's an array usingArray.isArray(x)
. - If
x
is an array, we need to dive deeper into its content:- Recursively call
flat
on elementx
, passing along the decremented depthn - 1
. This recursive call will returnx
flattened up ton - 1
layers. - Use the spread operator (
...
) to concatenate the elements returned by the recursive call to theans
array. This flattensx
one layer and merges its contents intoans
.
- Recursively call
- If
x
is not an array, simply pushx
ontoans
.
- Return Value:
- After iterating through all elements, return the
ans
array. Theans
array represents our multi-dimensional array flattened up to depthn
.
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 EvaluatorExample 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:
-
Base Case: Our function would first check if
n <= 0
. In this case,n
is1
, so we proceed with flattening. -
Initialization: We initialize an empty array
ans
. This will hold the partially flattened elements. -
Iteration:
- We begin by iterating through
arr
. The first element is[1, 2]
, which is an array.
- We begin by iterating through
-
Recursion and Concatenation:
- Since the first element
[1, 2]
is an array, we recursively callflat([1, 2], n - 1)
, which decrementsn
by1
. - The recursive call will return the array
[1, 2]
becausen
now becomes0
, which hits our base case. This array gets concatenated toans
, resulting inans = [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 depthn
at this point is0
(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 becomesans = [1, 2, 3, [4, 5]]
. - The last element in
arr
is6
. It is not an array, so we directly add6
toans
, resulting inans = [1, 2, 3, [4, 5], 6]
.
- Since the first element
-
Return Value: We have finished iterating through
arr
, and we returnans
. The final result is a flattened array up to depth1
:
[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 newans
array. Given that the maximum depth of recursion isn
, the space complexity due to recursive calls isO(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.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Want a Structured Path to Master System Design Too? Donāt Miss This!