
Problem Statement
Given a multi-dimensional array arr
and a non-negative integer n
representing the depth, flatten the array up to depth n
. A multi-dimensional array can contain both integers and other nested arrays. Flattening replaces any sub-array whose depth is less than n
with its elements.
You must not use built-in methods like Array.flat
. Instead, manually implement the flattening logic using recursion or iteration.
Examples
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:
With n = 0, no sub-arrays are flattened. Every element remains at its original depth.
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:
Sub-arrays at depth 0 are flattened. The nested array [9, 10, 11] remains unflattened since it's at depth 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:
All sub-arrays are within depth < 2, so the entire array is flattened.
Constraints
0 <= count of numbers in arr <= 10^5
0 <= count of sub-arrays in arr <= 10^5
0 <= n <= 1000
-1000 <= each number <= 1000
maxDepth <= 1000
Approach and Intuition
To solve this, we need a recursive approach that flattens the array layer by layer, only if the current depth is less than n
.
Depth-Aware Traversal:
- Use a recursive function that accepts the current
element
and itscurrentDepth
.
- Use a recursive function that accepts the current
Flatten Condition:
- If the current element is an array and
currentDepth < n
, we flatten it by recursively processing its items. - If it's not an array or the max depth is reached, we simply append it.
- If the current element is an array and
Edge Cases:
- If
n = 0
, no flattening should occur. - Arrays that contain no sub-arrays should return unchanged for any
n
.
- If
This recursive flattening ensures only desired depths are flattened while preserving deeper structures.
Solutions
- JavaScript
/**
* @param {any[]} array
* @param {number} level
* @return {any[]}
*/
var flatten = function (array, level) {
const tempStack = [...array.map((element) => [element, level])];
const result = [];
while (tempStack.length > 0) {
const [current, depth] = tempStack.pop();
if (Array.isArray(current) && depth > 0) {
tempStack.push(...current.map((x) => [x, depth - 1]));
} else {
result.push(current);
}
}
return result.reverse();
};
The provided JavaScript function, flatten
, is designed to flatten a deeply nested array up to a specified depth. When faced with a complex array structure that may consist of multiple levels of nesting, this function offers a practical way to either completely or partially flatten these levels into a simpler array structure. The function takes two parameters: array
, which is the nested array to be flattened, and level
, which determines the depth of flattening.
Here's an explanation of the function's core logic:
Initialize a temporary stack,
tempStack
, to store array elements along with their respective depths. The initial stack is filled with each top-level element paired with the specified flatten level using themap
function.Define an empty array,
result
, to hold the final flattened array.Process each element in
tempStack
using awhile
loop:Extract the element and its depth using array destructuring.
If the current element is itself an array and the depth is greater than 0:
- Decrease the depth by 1 for each element inside this nested array and push these elements back onto the stack.
If the element is not an array or the depth is 0, push the element directly into the
result
array.
Since elements were pushed last-to-first into the
result
, reverse it before returning to get elements in the original nested order.
The flatten
function efficiently processes deeply nested structures through iterative depth checking and handling, avoiding calls that might exceed the call stack if implemented recursively. This approach is particularly effective in environments where stack size might be a concern, such as in web browsers or extensive data processing applications.
No comments yet.