Flatten Deeply Nested Array #5 Most Asked

Medium

1 view

Topics:

ArraysRecursion

Given a multi-dimensional array arr and a depth n, return a flattened version of that array.

A multi-dimensional array is a recursive data structure that contains integers or other multi-dimensional arrays.

A flattened array is a version of that array with some or all of the sub-arrays removed and replaced with the actual elements in that sub-array. This flattening operation should only be done if the current depth of nesting is less than n. The depth of the elements in the first array are considered to be 0.

Please solve it without the built-in Array.flat method.

Example 1:

Input
arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]
n = 0
Output
[1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]

Explanation
Passing a depth of n=0 will always result in the original array. This is because the smallest possible depth of a subarray (0) is not less than n=0. Thus, no subarray should be flattened.

Example 2:

Input
arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]
n = 1
Output
[1, 2, 3, 4, 5, 6, 7, 8, [9, 10, 11], 12, 13, 14, 15]

Explanation
The subarrays starting with 4, 7, and 13 are all flattened. This is because their depth of 0 is less than 1. However [9, 10, 11] remains unflattened because its depth is 1.

Example 3:

Input
arr = [[1, 2, 3], [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]
n = 2
Output
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Explanation
The maximum depth of any subarray is 1. Thus, all of them are flattened.

Constraints:

0 <= count of numbers in arr <= 10⁵
0 <= count of subarrays in arr <= 10⁵
maxDepth <= 1000
-1000 <= each number <= 1000
0 <= n <= 1000

Try coding it in LeetCode

Flatten Deeply Nested Array #5 Most Asked

Medium

Rivian

1 view

Topics:

ArraysRecursion

Given a multi-dimensional array arr and a depth n, return a flattened version of that array.

A multi-dimensional array is a recursive data structure that contains integers or other multi-dimensional arrays.

A flattened array is a version of that array with some or all of the sub-arrays removed and replaced with the actual elements in that sub-array. This flattening operation should only be done if the current depth of nesting is less than n. The depth of the elements in the first array are considered to be 0.

Please solve it without the built-in Array.flat method.

Example 1:

Input
arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]
n = 0
Output
[1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]

Explanation
Passing a depth of n=0 will always result in the original array. This is because the smallest possible depth of a subarray (0) is not less than n=0. Thus, no subarray should be flattened.

Example 2:

Input
arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]
n = 1
Output
[1, 2, 3, 4, 5, 6, 7, 8, [9, 10, 11], 12, 13, 14, 15]

Explanation
The subarrays starting with 4, 7, and 13 are all flattened. This is because their depth of 0 is less than 1. However [9, 10, 11] remains unflattened because its depth is 1.

Example 3:

Input
arr = [[1, 2, 3], [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]
n = 2
Output
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Explanation
The maximum depth of any subarray is 1. Thus, all of them are flattened.

Constraints:

0 <= count of numbers in arr <= 10⁵
0 <= count of subarrays in arr <= 10⁵
maxDepth <= 1000
-1000 <= each number <= 1000
0 <= n <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the data type of the elements within the nested arrays? Can they be other than numbers, such as strings or other data structures?
Can the depth 'n' be zero? What should the output be in that case?
What should happen if the given depth 'n' is larger than the maximum nesting depth of the input array?
Is the input array guaranteed to be a valid array, or could it be null or undefined? What should I return in those cases?
Does the order of elements need to be preserved during flattening?

Brute Force Solution

Approach

Imagine you have a container that can hold only single items, but inside you have boxes, and some of those boxes might have more boxes inside them. To flatten the structure, we're going to unpack everything, level by level, until we only have single items in the main container. We will check each element and if the element is a box, we open it, and repeat.

Here's how the algorithm would work step-by-step:

Look at the first thing in your structure.
If it's a single item, put it directly into a new, single container.
If it's a box (or nested structure), open that box.
Now look at the first thing *inside* that opened box.
Repeat steps 2-4 until you find an item that is not a box. Then put it into the main single container.
Keep repeating steps 2-5 for all the items in the current box.
Once a box is completely empty, go back to processing the box that held the previous box.
Keep repeating this process until there are no more boxes to open and every single item is in the main single container.

Code Implementation

def flatten_deeply_nested_array(nested_array):
    flattened_array = []
    stack_of_arrays = [nested_array]

    while stack_of_arrays:
        current_array = stack_of_arrays.pop()
        for element in current_array:
            # Check if the current element is a list
            if isinstance(element, list):
                # Add current element (which is a list) to the stack to process
                stack_of_arrays.append(element)

            else:
                #If it is not a list add it to the result
                flattened_array.append(element)

    return flattened_array

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through each element of the potentially deeply nested array. Each element, whether it's a single item or another array, is visited and processed exactly once. The time taken to process a single element is constant. Therefore, the time complexity is directly proportional to the total number of elements, regardless of the nesting depth, resulting in O(n) time complexity, where n is the total number of elements in the flattened array.

Space Complexity

O(D) – The space complexity is determined by the maximum depth of nested arrays, where each nested array adds a layer to the call stack during the recursive 'opening' process described. In the worst case, where the array is deeply nested to a depth of 'D', the recursion will create 'D' stack frames. Each stack frame stores information about the current state of the array being processed. Therefore, the auxiliary space required scales linearly with the maximum nesting depth, 'D', resulting in O(D) space complexity.

Optimal Solution

Approach

The best way to flatten a deeply nested array is to go through each element one by one and, if you find an array, open it up and repeat the process on its contents. This continues until you're only left with individual, non-array elements. It's like peeling an onion layer by layer until you reach the core.

Here's how the algorithm would work step-by-step:

Start with an empty container to hold the flattened result.
Look at the first thing in the original array.
If it's not an array (like a number or a word), simply put it into your flattened result container.
If it is an array, don't just add the array itself. Instead, take everything *inside* that array and repeat this entire process on each of those items.
Keep doing this, going deeper and deeper into nested arrays, until there are no more arrays left to unpack.
The container now holds every original element, but none of them are trapped inside arrays anymore; everything is at the same level.

Code Implementation

def flatten_deeply_nested_array(input_array):
    flattened_result = []

    def process_element(element):
        # Check if the current element is a list (array).
        if isinstance(element, list):

            # Recursively process each item within the list.
            for item in element:
                process_element(item)

        else:
            # Append non-list elements to the flattened result.
            flattened_result.append(element)

    # Iterate through the input array to start the process.
    for element in input_array:
        process_element(element)

    return flattened_result

Big(O) Analysis

Time Complexity

O(n) – The algorithm visits each element in the input array and its nested arrays exactly once. While nested arrays require further processing, each element within those arrays is also visited only once. Therefore, the number of operations is directly proportional to the total number of elements across all nested levels, which we can denote as n. Thus, the time complexity is O(n).

Space Complexity

O(D) – The algorithm uses a call stack to keep track of the nested arrays during recursion. In the worst-case scenario, where the array is deeply nested to a depth of D, the recursion stack will grow proportionally to D, where D is the maximum nesting depth of the input array. The space used for the call stack will thus be D. Therefore, the auxiliary space complexity is O(D).

Edge Cases

Case	How to Handle
Input array is null or undefined	Return an empty array to gracefully handle invalid input.
Input array is empty	Return the empty array directly as there's nothing to flatten.
Depth n is 0	Return the original array without any flattening.
Depth n is a very large number or infinity	Treat n as fully flattening the array until no sub-arrays are left.
Input array contains non-array elements at the top level (e.g., numbers, strings)	Treat non-array elements as already flattened and include them in the output array.
Input array contains nested empty arrays	Handle nested empty arrays by skipping them during flattening.
Input array contains mixed data types within nested arrays (numbers, strings, booleans, objects)	Include all elements of any type during flattening.
Deeply nested array exceeding maximum call stack size (if using recursion)	Consider an iterative approach using a stack to avoid stack overflow errors.

Input array is null or undefined

How to Handle:

Return an empty array to gracefully handle invalid input.

Input array is empty

How to Handle:

Return the empty array directly as there's nothing to flatten.

Depth n is 0

How to Handle:

Return the original array without any flattening.

Depth n is a very large number or infinity

How to Handle:

Treat n as fully flattening the array until no sub-arrays are left.

Input array contains non-array elements at the top level (e.g., numbers, strings)

How to Handle:

Treat non-array elements as already flattened and include them in the output array.

Input array contains nested empty arrays

How to Handle:

Handle nested empty arrays by skipping them during flattening.

Input array contains mixed data types within nested arrays (numbers, strings, booleans, objects)

How to Handle:

Include all elements of any type during flattening.

Deeply nested array exceeding maximum call stack size (if using recursion)

How to Handle:

Consider an iterative approach using a stack to avoid stack overflow errors.