Flatten Deeply Nested Array - Leetcode Solution

Problem Statement: Given a deeply nested array of integers, write a function to flatten the array, so that all the integers appear at the top level of the array. The input array can have an arbitrary number of levels of nesting.

Example: Input: [1, 2, [3, 4, [5, 6], 7], 8] Output: [1, 2, 3, 4, 5, 6, 7, 8]

Solution Approach: The basic idea behind solving the problem is to use recursion, by recursing through the given array and flattening the nested arrays until all the elements are at the top level.

Algorithm:

1. Create an empty result array variable.
2. For each element in the input array:
   • If the element is an array, recursively call the flatten function on it and append the flattened result to the result array.
   • If the element is not an array, simply append it to the result array.
3. Return the result array.

Pseudo Code:

function flatten(arr):
    result = []
    for element in arr:
        if element is an array:
            result += flatten(element)
        else:
            result += element
    return result

Time Complexity: The time complexity of the flatten function is O(n), where n is the total number of elements in the input array. Since we have to visit each element of the input array once. The time complexity can be further optimized with the help of memoization, but that is not required in this specific problem.

Space Complexity: The space complexity of the flatten function is also O(n), where n is the total number of elements in the input array. The space complexity can also be further optimized with the help of memoization, but that is not required in this specific problem.

Coding Solution (Python):

def flatten(arr):
    result = []
    for element in arr:
        if isinstance(element, list):
            result += flatten(element)
        else:
            result.append(element)
    return result

Coding Solution (JavaScript):

function flatten(arr) {
    let result = [];
    for (let element of arr) {
        if (Array.isArray(element)) {
            result = [...result, ...flatten(element)];
        } else {
            result.push(element);
        }
    }
    return result;
}

I hope this helps!

1