Flatten Deeply Nested Array

Updated on 30 May, 2025
Flatten Deeply Nested Array header image

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.

  1. Depth-Aware Traversal:

    • Use a recursive function that accepts the current element and its currentDepth.
  2. 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.
  3. Edge Cases:

    • If n = 0, no flattening should occur.
    • Arrays that contain no sub-arrays should return unchanged for any n.

This recursive flattening ensures only desired depths are flattened while preserving deeper structures.

Solutions

  • JavaScript
js
/**
 * @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:

  1. 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 the map function.

  2. Define an empty array, result, to hold the final flattened array.

  3. Process each element in tempStack using a while 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.

  4. 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.

Comments

No comments yet.