Problem

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.

Examples

Example 1

1
2
3
4
5
6
7
8

**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

1
2
3
4
5
6
7
8

**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

1
2
3
4
5
6
7
8

**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^5
  • 0 <= count of subarrays in arr <= 10^5
  • maxDepth <= 1000
  • -1000 <= each number <= 1000
  • 0 <= n <= 1000

Solution

Method 1 – Recursive Depth-Limited Flattening

Intuition

The key idea is to recursively traverse the array, flattening subarrays only if their current depth is less than the given limit n. This ensures that subarrays at or above the depth limit remain nested.

Approach

  1. Define a helper function that takes the current array and its depth.
  2. For each element in the array:
    • If it is an integer, add it to the result.
    • If it is an array and the current depth is less than n, recursively flatten it with depth + 1 and add its elements to the result.
    • If it is an array and the current depth is n or more, add the subarray as is.
  3. Return the result array.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
  flatten(arr, n) {
    function helper(a, d) {
      let ans = [];
      for (let el of a) {
        if (Array.isArray(el) && d < n) {
          ans.push(...helper(el, d + 1));
        } else {
          ans.push(el);
        }
      }
      return ans;
    }
    return helper(arr, 0);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
  flatten(arr: any[], n: number): any[] {
    function helper(a: any[], d: number): any[] {
      let ans: any[] = [];
      for (let el of a) {
        if (Array.isArray(el) && d < n) {
          ans.push(...helper(el, d + 1));
        } else {
          ans.push(el);
        }
      }
      return ans;
    }
    return helper(arr, 0);
  }
}

Complexity

  • ⏰ Time complexity: O(m) where m is the total number of elements (including all nested elements), since each element is visited once.
  • 🧺 Space complexity: O(m) due to recursion stack and the result array.