Problem Description

You are given a multi-dimensional array arr and a depth value n. Your task is to flatten this array up to the specified depth level.

A multi-dimensional array is a nested structure that can contain integers or other arrays within it. For example, [1, [2, 3], [[4]]] is a multi-dimensional array with different levels of nesting.

The flattening operation should remove array brackets and expose the elements inside, but only up to depth n. The depth counting starts at 0 for elements in the outermost array.

Here's how depth works:

• Elements at the top level have depth 0
• Elements inside one level of nesting have depth 1
• Elements inside two levels of nesting have depth 2, and so on

When flattening with depth n:

• If an element's current depth is less than n and it's an array, unwrap it
• If an element's current depth equals or exceeds n, keep it as is
• If an element is not an array, keep it as is

For example:

• arr = [1, 2, [3, 4, [5, 6]]] with n = 0 returns [1, 2, [3, 4, [5, 6]]] (no flattening)
• arr = [1, 2, [3, 4, [5, 6]]] with n = 1 returns [1, 2, 3, 4, [5, 6]] (flatten one level)
• arr = [1, 2, [3, 4, [5, 6]]] with n = 2 returns [1, 2, 3, 4, 5, 6] (flatten two levels)

You must implement this without using JavaScript's built-in Array.flat() method.

Intuition

The key insight is to think of this problem recursively. When we encounter an array element while iterating through the input, we need to decide whether to unwrap it or keep it as is. This decision depends on how many levels deep we're allowed to flatten (the value of n).

Think of n as a "budget" for how many levels we can unwrap. Each time we go one level deeper into nested arrays, we spend one unit from this budget. When n reaches 0, we stop unwrapping and keep everything as is.

The recursive approach naturally emerges from this observation:

1. If n = 0, we've exhausted our flattening budget, so return the array unchanged
2. Otherwise, iterate through each element:
   • If it's an array and we still have budget (n > 0), recursively flatten it with n - 1 (using one unit of our budget)
   • If it's not an array, just add it to our result

The spread operator (...) is perfect here because when we recursively flatten a sub-array, we want to insert all its elements into our result array, not the sub-array itself as a single element.

For example, with [1, [2, [3]]] and n = 1:

• Process 1: not an array, add it → [1]
• Process [2, [3]]: it's an array and n = 1, so recursively flatten with n = 0
  • In the recursive call with n = 0, return [2, [3]] unchanged
  • Spread these elements into our result → [1, 2, [3]]

This way, each recursive call handles one level of depth, decrementing n as we go deeper, until we either run out of budget or run out of nested arrays to flatten.

Solution Approach

The implementation uses a recursive approach to flatten the array up to the specified depth. Let's walk through the solution step by step:

Base Case:

if (!n) {
    return arr;
}

When n is 0, we've reached our flattening limit. Return the array as-is without any further processing.

Recursive Processing:

const ans: MultiDimensionalArray = [];
for (const x of arr) {
    if (Array.isArray(x) && n) {
        ans.push(...flat(x, n - 1));
    } else {
        ans.push(x);
    }
}

We create a new result array ans and iterate through each element x in the input array:

1. If the element is an array and we have remaining depth (Array.isArray(x) && n):

   • Recursively call flat(x, n - 1) to flatten this sub-array with one less depth level
   • Use the spread operator ... to push all returned elements into ans
   • The n - 1 decrements our depth budget for the recursive call

2. If the element is not an array OR we've exhausted our depth:

   • Simply push the element as-is into ans
   • This preserves non-array values (numbers) and arrays that shouldn't be flattened further

Example Walkthrough:

For arr = [1, [2, [3, 4]]] with n = 1:

• First call: flat([1, [2, [3, 4]]], 1)
  • Process 1: not an array → push 1 to result
  • Process [2, [3, 4]]: is array and n = 1 → call flat([2, [3, 4]], 0)
    • Second call: flat([2, [3, 4]], 0)
      • Since n = 0, return [2, [3, 4]] unchanged
    • Spread [2, [3, 4]] into result
  • Final result: [1, 2, [3, 4]]

The time complexity is O(N) where N is the total number of elements across all nesting levels, as we visit each element once. The space complexity is O(D) where D is the maximum depth of nesting, due to the recursive call stack.

Example Walkthrough

Let's trace through a concrete example to understand how the recursive flattening works.

Example: arr = [1, [2, 3], [[4]]] with n = 1

Initial Call: flat([1, [2, 3], [[4]]], 1)

• n = 1, so we proceed with flattening
• Create empty result array: ans = []

Processing each element:

1. Element 1:

   • Not an array → push directly to ans
   • ans = [1]

2. Element [2, 3]:

   • Is an array AND n = 1 → recursively call flat([2, 3], 0)

   Recursive Call: flat([2, 3], 0)

   • n = 0 → base case reached

   • Return [2, 3] unchanged

   • Back in main call: spread [2, 3] into ans

   • ans = [1, 2, 3]

3. Element [[4]]:

   • Is an array AND n = 1 → recursively call flat([[4]], 0)

   Recursive Call: flat([[4]], 0)

   • n = 0 → base case reached

   • Return [[4]] unchanged

   • Back in main call: spread [[4]] into ans

   • ans = [1, 2, 3, [4]]

Final Result: [1, 2, 3, [4]]

Notice how:

• The first-level arrays [2, 3] and [[4]] were unwrapped (their brackets removed)
• The second-level array [4] remained intact because we only flattened to depth 1
• Each recursive call decremented n by 1, controlling how deep we flatten

Solution Implementation

Time and Space Complexity

Time Complexity: O(N) where N is the total number of elements (including nested elements) in the input array.

The algorithm visits each element in the multi-dimensional array exactly once. Even though the function is recursive and may process arrays at different nesting levels, each element is only processed once when it's encountered. The push(...flat(x, n - 1)) operation spreads the results, but the recursive call itself only processes each element once. Therefore, if there are N total elements across all nesting levels, the time complexity is linear.

Space Complexity: O(N) where N is the total number of elements in the input array.

The space complexity consists of two components:

1. Output array space: The ans array will eventually contain all elements from the input array (flattened to the specified depth), requiring O(N) space.
2. Recursive call stack: In the worst case, when we have deeply nested arrays up to depth n, the call stack can grow up to O(n) levels deep. However, since n represents the flattening depth (not the total elements), and is typically much smaller than N, this is dominated by the output array space.

The overall space complexity is O(N) as the output array dominates the space usage.

Common Pitfalls

1. Mutating the Original Array

A common mistake is trying to modify the input array in-place instead of creating a new array. This can lead to unexpected side effects if the original array is used elsewhere in the code.

Incorrect Approach:

def flat(arr, n):
    if n == 0:
        return arr
  
    i = 0
    while i < len(arr):
        if isinstance(arr[i], list) and n > 0:
            # This modifies the original array!
            arr[i:i+1] = flat(arr[i], n - 1)
            i += len(arr[i])
        else:
            i += 1
    return arr

Solution: Always create a new result array and avoid modifying the input array.

2. Incorrect Depth Check Logic

Developers often confuse when to stop flattening. A common error is checking n <= 0 after already entering the recursive call, or using the wrong comparison operator.

Incorrect Approach:

def flat(arr, n):
    result = []
    for element in arr:
        # Wrong: should check n > 0, not n >= 0
        if isinstance(element, list) and n >= 0:
            result.extend(flat(element, n - 1))
        else:
            result.append(element)
    return result

This would flatten one level too deep because when n = 0, it still attempts to flatten.

Solution: Use the correct condition n > 0 or implement the base case check at the beginning of the function.

3. Not Handling Edge Cases Properly

Failing to handle empty arrays or negative depth values can cause unexpected behavior.

Problematic Scenarios:

# Empty nested arrays might be handled incorrectly
flat([[], [[]]], 1)  # Should return [[], []]

# Negative depth values
flat([1, [2, 3]], -1)  # Should return [1, [2, 3]] unchanged

Solution: Add proper validation:

def flat(arr, n):
    # Handle negative or zero depth
    if n <= 0:
        return arr
  
    result = []
    for element in arr:
        if isinstance(element, list):
            result.extend(flat(element, n - 1))
        else:
            result.append(element)
    return result

4. Type Checking Confusion

In Python, using type(element) == list instead of isinstance(element, list) can cause issues with list subclasses or when dealing with different array-like structures.

Incorrect Approach:

def flat(arr, n):
    if n == 0:
        return arr
  
    result = []
    for element in arr:
        # This might miss list subclasses
        if type(element) == list and n > 0:
            result.extend(flat(element, n - 1))
        else:
            result.append(element)
    return result

Solution: Use isinstance() for more robust type checking that handles inheritance properly.

5. Forgetting to Decrement Depth in Recursive Call

A critical error is passing the same depth value to recursive calls instead of decrementing it.

Incorrect Approach:

def flat(arr, n):
    if n == 0:
        return arr
  
    result = []
    for element in arr:
        if isinstance(element, list):
            # Wrong: passing n instead of n - 1
            result.extend(flat(element, n))  
        else:
            result.append(element)
    return result

This creates infinite recursion for nested arrays when n > 0.

Solution: Always decrement the depth parameter when making recursive calls: flat(element, n - 1).