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 <= 1050 <= count of subarrays in arr <= 105maxDepth <= 1000-1000 <= each number <= 10000 <= n <= 1000The idea behind this approach is to use recursion to flatten the array up to the specified depth n. If the current depth is less than n, we continue flattening; otherwise, we do not flatten further. We leverage recursive calls to process each element and manage the depth level.
This C solution uses mock conditions/flags to illustrate how you might handle subarray occurrences in a real scenario where int arrays don't inherently distinguish subarrays. A recursive helper function processes elements while managing the depth level. This mock example assumes a simple subarray flag (-1) just for demonstration purposes.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m) where m is the total number of elements in the array considering all levels.
Space Complexity: O(m) due to recursive stack space and storage of flattened elements.
This technique leverages a stack data structure to simulate recursion iteratively. By using an explicit stack, we can iteratively flatten the array, taking control of the depth level without using the actual recursive calls within the stack frames.
This iterative C solution uses a stack to manage array processing, avoiding direct recursion. This mock setup involves using markers and demonstrates how such a stack could work for real subarrays. It pushes all values and sub-arrays into a custom stack, managing the depth manually.
C++
Java
Python
C#
JavaScript
Time Complexity: O(m), iterating through each array element.
Space Complexity: O(m) due to storage in stack elements.
| Approach | Complexity |
|---|---|
| Recursive Flattening up to Depth | Time Complexity: O(m) where m is the total number of elements in the array considering all levels. |
| Iterative Flattening with Depth Control | Time Complexity: O(m), iterating through each array element. |
I solved too many Leetcode problems • NeetCodeIO • 101,495 views views
Watch 9 more video solutions →Practice Flatten Deeply Nested Array with our built-in code editor and test cases.
Practice on FleetCode