# 2625. Flatten Deeply Nested Array ###### tags: `leetcode 30 days js challenge` `Medium` [2625. Flatten Deeply Nested Array](https://leetcode.com/problems/flatten-deeply-nested-array/) ### 題目描述 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<sup>5</sup> - 0 <= count of subarrays in arr <= 10<sup>5</sup> - `maxDepth <= 1000` - `-1000 <= each number <= 1000` - `0 <= n <= 1000` ### 解答 #### TypeScript (recursive) ```typescript= function flat(arr: MultiDimensionalArray, n: number): MultiDimensionalArray { const flattened: MultiDimensionalArray = []; for (const element of arr) { if (Array.isArray(element) && n > 0) { flat(element, n - 1).forEach((d) => flattened.push(d)); } else { flattened.push(element); } } return flattened; } ``` > [name=Sheep][time=Fri, May 26, 2023] #### TypeScript (stack) ```typescript= function flat(arr: MultiDimensionalArray, n: number): MultiDimensionalArray { const stack: [MultiDimensionalArray | number, number][] = arr.map((item) => [item, n]); const result: MultiDimensionalArray = []; while (stack.length > 0) { const [item, depth] = stack.pop() as [MultiDimensionalArray | number, number]; if (Array.isArray(item) && depth > 0) { stack.push(...item.map((el) => [el, depth - 1] as [MultiDimensionalArray, number])); } else { result.push(item); } } return result.reverse(); } ``` > [name=Sheep][time=Fri, May 26, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)