Watch 10 video solutions for Flatten Deeply Nested Array, a medium level problem. This walkthrough by NeetCodeIO has 11,003 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 1000Problem Overview: You receive an array that may contain integers or other arrays nested at multiple levels. The task is to flatten the structure up to a given depth n. Elements deeper than n levels must remain nested, while everything within that depth becomes part of a single array.
Approach 1: Recursive Flattening up to Depth (Time: O(n), Space: O(n))
This approach directly mirrors the nested structure using recursion. Iterate through the array and check each element. If the element is an array and the remaining depth is greater than zero, recursively flatten that subarray with depth - 1. Otherwise, append the element to the result. Every element is visited once, which gives an overall O(n) time complexity where n is the total number of elements across all nested arrays. The recursion stack may grow up to the maximum nesting level, resulting in O(n) auxiliary space in the worst case.
This method is clean and intuitive. The recursive calls naturally handle nested structures without additional data structures. If you're comfortable with recursion, this solution is usually the fastest to implement during interviews.
Approach 2: Iterative Flattening with Depth Control (Time: O(n), Space: O(n))
The iterative approach replaces the recursion stack with an explicit stack or queue. Iterate through the array while tracking the remaining flatten depth for each element. When encountering a nested array and the allowed depth is still positive, push its contents back into the stack with depth - 1. Otherwise, append the element to the output array. This simulates the recursive traversal but avoids function call overhead.
Each element is still processed once, so the time complexity remains O(n). The explicit stack may temporarily store elements from nested arrays, leading to O(n) space in the worst case. This method relies on a classic stack-based traversal of nested structures and works well when recursion depth might become large.
Since the problem fundamentally deals with nested list traversal, both solutions rely heavily on understanding arrays and hierarchical structures.
Recommended for interviews: The recursive approach is usually expected first because it directly models the nested structure and is easy to reason about. Interviewers often accept it as the primary solution. The iterative stack-based approach demonstrates deeper control over traversal mechanics and avoids recursion limits, which can be valuable when discussing scalability or language stack constraints.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Flattening up to Depth | O(n) | O(n) | Best when recursion depth is manageable and you want the simplest implementation |
| Iterative Flattening with Stack | O(n) | O(n) | Useful when avoiding recursion limits or when explicit control over traversal is preferred |