2625. Flatten Deeply Nested Array

Array implementation

Description

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 cases

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

Approach

javascript의 built-in 함수 Array.prototype.flat() 을 구현하는 문제이다
재귀적 접근방법을 통해 $O(n)$ 으로 해결할 수 있다.
아이디어는 전체 배열을 한번 순회하면서 Array.isArray로 해당 값이 배열인지 판단하여 배열이 아니면 그대로 그 값은 push하고, 배열이면 해당 배열을 재귀적으로 호출한다
재귀에서 중요한 종료 조건은 두번째 인자로 현재 depth를 넘겨주는데 이 값이 0이면 더 이상 들어가지 않고 그대로 concat을 통해 정답 배열에 넣는다.
이런식으로 하면 주어진 depth가 몇 인지 관계 없이 결과적으로 모든 원소를 한번 검사하는걸로 알고리즘은 끝난다.

Solution Code

var flat = function (arr, n) {
  if (n === 0) return arr
  let ans = []
 
  const flatten = (a, n) => {
      if (n === 0) {
        ans = ans.concat(a)
        return
      }
 
      for (let i = 0; i < a.length; i += 1) {
          if (Array.isArray(a[i])) {
              flatten(a[i], n - 1)
          } else {
              ans.push(a[i])
          }
      }
  }
 
  flatten(arr, n)
 
  return ans
};

Complexity

time complexity : $O(n)$
space complexity : $O(n)$

151. Reverse Words in a String 75. Sort Colors