2625. Flatten Deeply Nested Array - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

Given a multi‑dimensional array arr and an integer n, return a flattened version of arr up to depth n. Flattening means that for any sub‑array whose nesting depth (starting at 0 for the top‑level arr) is less than n, you replace that sub‑array with its individual elements. Do not use the built‑in Array.flat method.

Examples

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: depth 0 means “don’t flatten anything.”

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: only sub‑arrays at depth 0 get flattened; deeper ones stay nested.

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 up to depth 1 are flattened, which here empties all nesting.

Constraints

Total number of integers and sub‑arrays combined ≤ 10⁵
0 ≤ n ≤ 1000
Maximum nesting depth of arr ≤ 1000
Each integer in arr is between -1000 and 1000

Hints

How would you “unwrap” the top level of nesting? What changes when you go one level deeper?
Could you write a helper function that carries along the current depth and decides whether to recurse or emit the element directly?

Approach 1 Recursive Depth‑First Flattening

Explanation

Use a helper dfs(subArr, depth) that walks through each element of subArr. If an element is itself an array and depth < n, recurse into it with depth+1; otherwise push the element (or the sub‑array object) onto your result.

Step‑by‑step Walkthrough

Call dfs(arr, 0).
For each item in arr:
- If item is a list and current depth < n, call dfs(item, depth+1).
- Else, append item to result.
Return result after the traversal.

Visual Example

arr = [1, [2, [3]], 4], n = 1
dfs([1, [2, [3]], 4], 0):
  1 → push 1
  [2, [3]] and depth=0<1 → dfs([2, [3]],1):
    2 → push 2
    [3] but depth=1==n → push [3] as array
  4 → push 4
Result = [1, 2, [3], 4]

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity Analysis

Time O(M) where M = total count of elements and sub‑arrays (each visited once)
Space O(M + D) for the output plus recursion stack of depth D = min(n, nesting depth)

Approach 2 Iterative Stack⁠‑Based Flattening

Explanation

Simulate recursion with an explicit stack of (subList, index, depth) frames. Pop a frame, process its current element, and push new frames for nested arrays when depth < n.

Python Sketch

Python3

. . . .

Complexity

Same O(M) time and O(M) space for result plus O(D) stack frames.

Common Mistakes

Forgetting to stop flattening when depth == n, causing full flattening instead of limited depth
Not handling n = 0 (should return the original structure)
Modifying the input list in place rather than building a new result