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 goal of #2625 Flatten Deeply Nested Array is to transform a nested array into a flattened structure up to a specified depth n. Instead of fully flattening every level, only the first n nesting levels should be expanded. This requires careful traversal of the array while tracking the remaining depth.
A common strategy is to use recursion. For each element, check if it is an array and whether the remaining depth is greater than zero. If so, recursively process its elements with depth reduced by one. Otherwise, append the element directly to the result. Another efficient alternative is an iterative approach using a stack, which simulates recursion and helps manage nested structures explicitly.
Both approaches ensure each element is processed once, leading to efficient performance. The key challenge is correctly managing the depth limit while preserving element order during traversal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Recursive Traversal | O(n) | O(d) |
| Iterative Stack-Based | O(n) | O(d) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Write a recursive function that keeps track of the current depth.
if the current depth >= the maximum depth, always just push the value to the returned array. Otherwise recursively call flat on the array.
The 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.
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.
1import java.util.ArrayList;
2import java.util.List;
3
4public class FlattenArray {
5 public static
This Java implementation uses a recursive helper method to iterate over each element. When encountering a nested list, it checks the current depth against the flatten threshold. If within range, recursion continues; otherwise, cascades sub-elements directly.
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.
Time Complexity: O(m), iterating through each array element.
Space Complexity: O(m) due to storage in stack elements.
1
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, variations of array flattening problems frequently appear in FAANG-style interviews. They test recursion, stack usage, and understanding of nested data structures.
In most implementations, flattening a nested array takes O(n) time because every element must be visited at least once. The extra space depends on recursion depth or stack usage.
Arrays combined with either recursion or a stack work best for this problem. A stack is particularly useful in iterative solutions to manage nested elements and simulate recursive behavior.
The optimal approach is typically recursion or an iterative stack-based traversal. Both methods process each element once while tracking the remaining flatten depth, resulting in O(n) time complexity.
Python’s stack-based solution iterates over the input list using a manual stack. Given tuples holding both the current list and index, flatten_array() evaluates depth to determine their inclusion, breaking into subarrays where appropriate.