LeetCode 2625 - Flatten Deeply Nested Array

LeetCode Problem 2625

Difficulty: 🟡 Medium
Topics: —

Solution

This problem is implemented in JavaScript on LeetCode, but you requested Python and Go reference solutions. Since the original stub uses JavaScript-style nested arrays with mixed integer/array values, I will model the structure idiomatically in Python and Go while keeping the logic fully LeetCode-submittable.

Problem Understanding

The problem asks us to flatten a multi-dimensional array, but only up to a limited depth n.

A multi-dimensional array is recursively defined. Each element may either be an integer or another array that itself may contain integers or additional nested arrays. The task is to remove nested array boundaries, but only while the current nesting depth is strictly less than n.

The phrase "depth of nesting is less than n" is the key detail that determines when flattening stops.

We begin at depth 0, which corresponds to the top-level array. If we encounter a nested subarray at a depth smaller than n, we flatten it by replacing the subarray with its contents. Once we reach depth n, we stop flattening and preserve any remaining nested arrays exactly as they are.

For example, if n = 0, nothing gets flattened because even the shallowest nested arrays are already at depth 0, and 0 < 0 is false.

If n = 1, arrays directly inside the top-level array are flattened because their depth is 0, which satisfies 0 < 1. However, arrays nested one level deeper are preserved because their depth becomes 1, and 1 < 1 is false.

The input consists of:

• arr, a recursively nested array structure containing integers and arrays
• n, the maximum flattening depth

The output should be a new flattened array where nested arrays have been expanded only up to the allowed depth.

The constraints reveal several important implementation details.

The total number of numbers and subarrays can each reach 10^5, meaning the overall structure may be very large. A naive repeated flattening approach that scans the array multiple times would likely become too slow.

The maximum nesting depth can be as large as 1000, which introduces another concern. Recursive solutions may risk stack overflow in some languages if implemented carelessly. However, depth 1000 is manageable in most practical recursion contexts, especially in Python if recursion limits are considered, though an iterative approach can also work.

Several edge cases deserve attention:

• n = 0, meaning the original array must remain unchanged.
• Empty arrays, which should simply contribute nothing to the output.
• Deeply nested structures where flattening stops before full expansion.
• Cases where n exceeds the maximum nesting depth, meaning the entire structure becomes fully flattened.
• Arrays containing only integers, where no flattening occurs regardless of n.

The problem guarantees valid input, meaning elements are always integers or nested arrays, so we do not need additional validation logic.

Approaches

Brute Force Approach

A straightforward approach is to repeatedly flatten the array one level at a time.

For each flattening pass, we iterate through the current array. If an element is a nested array, we expand it into the result. Otherwise, we append the integer directly.

We repeat this process exactly n times.

This works because each pass removes one level of nesting. After n iterations, the array has been flattened to the required depth.

However, this approach is inefficient. Every pass scans the entire structure again, even elements that were already processed previously. In the worst case, if n is large and the array is deeply nested, we may repeatedly traverse the same elements.

This repeated work makes the solution unnecessarily expensive.

Optimal Approach, Depth Controlled DFS

The key observation is that we do not need repeated flattening passes. Instead, we can traverse the structure once while tracking the current depth.

Whenever we encounter:

• An integer, we append it directly to the result.

• A nested array:

• If the current depth is less than n, we recursively explore its contents.

• Otherwise, we keep the subarray intact.

This works because flattening decisions depend only on the current nesting depth. By carrying depth information during traversal, we can decide immediately whether to flatten or preserve each subarray.

Since every element is visited only once, this eliminates repeated work and achieves optimal efficiency.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(m)	Repeatedly flattens one level at a time, rescans elements multiple times
Optimal	O(m)	O(m + d)	Single DFS traversal, each element processed once

Here:

• m is the total number of elements and nested arrays.
• d is the maximum recursion depth.

Algorithm Walkthrough

Optimal Algorithm

1. Create an empty result array.

This array will store the final flattened structure. 2. Define a recursive helper function.

The helper receives:

• The current subarray
• The current nesting depth

This allows us to decide whether flattening is still allowed. 3. Iterate through every element in the current array.

For each element, determine whether it is an integer or another array. 4. If the element is an integer, append it directly.

Numbers are always included in the result because flattening only affects array boundaries. 5. If the element is a nested array:

• If currentDepth < n, recursively process the nested array.

This effectively removes one layer of nesting.

• Otherwise, append the nested array as-is.

This preserves the structure once the flattening limit has been reached. 6. Start recursion from the top-level array with depth 0. 7. Return the result array after traversal completes.

Why it works

The algorithm maintains a simple invariant:

Every nested array encountered at depth smaller than n is flattened, while every array at depth n or greater remains intact.

Because the traversal visits every element exactly once and makes the flattening decision immediately based on depth, the resulting structure precisely matches the problem definition.

Python Solution

from typing import List, Union

NestedInteger = Union[int, List["NestedInteger"]]

class Solution:
    def flat(self, arr: List[NestedInteger], n: int) -> List[NestedInteger]:
        result: List[NestedInteger] = []

        def dfs(current_array: List[NestedInteger], depth: int) -> None:
            for element in current_array:
                if isinstance(element, list):
                    if depth < n:
                        dfs(element, depth + 1)
                    else:
                        result.append(element)
                else:
                    result.append(element)

        dfs(arr, 0)
        return result

The implementation follows the algorithm directly.

We first create a result list that will accumulate the flattened elements.

The nested dfs() function performs the recursive traversal. It receives the current subarray and the current depth.

Inside the loop, we distinguish between integers and lists using isinstance(element, list).

If the element is a list and flattening is still allowed, meaning depth < n, we recursively process its contents with depth + 1.

Otherwise, we preserve the nested list exactly as it appears by appending it to the result.

Finally, we begin traversal at depth 0 and return the completed result.

Go Solution

package main

func flat(arr []interface{}, n int) []interface{} {
	result := make([]interface{}, 0)

	var dfs func([]interface{}, int)

	dfs = func(currentArray []interface{}, depth int) {
		for _, element := range currentArray {
			if nestedArray, ok := element.([]interface{}); ok {
				if depth < n {
					dfs(nestedArray, depth+1)
				} else {
					result = append(result, nestedArray)
				}
			} else {
				result = append(result, element)
			}
		}
	}

	dfs(arr, 0)

	return result
}

The Go implementation mirrors the Python logic closely.

Since Go does not support mixed-type arrays naturally, we use []interface{} to represent the nested structure.

Type assertions are used to determine whether an element is another nested slice:

nestedArray, ok := element.([]interface{})

If the assertion succeeds, we know the element is a nested array and can decide whether to recurse or preserve it.

Unlike Python, Go requires explicit slice handling and function variable declaration for recursive anonymous functions.

There are no integer overflow concerns here because values remain within the problem constraints.

Worked Examples

Example 1

Input

arr = [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]
n = 0

Since depth < n becomes 0 < 0, which is false, no flattening occurs.

Element	Current Depth	Action	Result
1	0	Append	[1]
2	0	Append	[1, 2]
3	0	Append	[1, 2, 3]
[4,5,6]	0	Keep as-is	[1,2,3,[4,5,6]]
[7,8,[9,10,11],12]	0	Keep as-is	preserved
[13,14,15]	0	Keep as-is	final

Final output:

[1,2,3,[4,5,6],[7,8,[9,10,11],12],[13,14,15]]

Example 2

Input

arr = [1,2,3,[4,5,6],[7,8,[9,10,11],12],[13,14,15]]
n = 1

At depth 0, flattening is allowed.

Step	Element	Depth	Action	Result
1	1	0	Append	[1]
2	2	0	Append	[1,2]
3	3	0	Append	[1,2,3]
4	[4,5,6]	0	Recurse	[1,2,3,4,5,6]
5	[7,8,[9,10,11],12]	0	Recurse	continue
6	[9,10,11]	1	Preserve	remains nested
7	[13,14,15]	0	Recurse	final

Final output:

[1,2,3,4,5,6,7,8,[9,10,11],12,13,14,15]

Example 3

Input

arr = [[1,2,3],[4,5,6],[7,8,[9,10,11],12],[13,14,15]]
n = 2

All nested arrays appear at depth 0 or 1.

Since both depths satisfy depth < 2, every subarray gets flattened.

Depth	Action
0	Flatten top-level subarrays
1	Flatten [9,10,11]
2	No remaining nested arrays

Final output:

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m)	Every number and subarray is visited exactly once
Space	O(m + d)	Result storage plus recursion depth

Here, m represents the total number of elements and nested arrays, while d represents the maximum nesting depth.

The time complexity is linear because each element is processed only once during DFS traversal. There is no repeated scanning or reprocessing.

The extra space comes from two sources. The output array may contain up to all elements, and the recursion stack may grow as deep as the maximum nesting depth.

Test Cases

solution = Solution()

# Example 1, n = 0 means no flattening
assert solution.flat(
    [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]],
    0
) == [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]]

# Example 2, flatten one level
assert solution.flat(
    [1, 2, 3, [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]],
    1
) == [1, 2, 3, 4, 5, 6, 7, 8, [9, 10, 11], 12, 13, 14, 15]

# Example 3, flatten completely
assert solution.flat(
    [[1, 2, 3], [4, 5, 6], [7, 8, [9, 10, 11], 12], [13, 14, 15]],
    2
) == [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

# Empty array
assert solution.flat([], 5) == []

# Array with no nesting
assert solution.flat([1, 2, 3], 10) == [1, 2, 3]

# Single nested array with n = 0
assert solution.flat([[1, 2, 3]], 0) == [[1, 2, 3]]

# Single nested array with n = 1
assert solution.flat([[1, 2, 3]], 1) == [1, 2, 3]

# Deep nesting but limited flatten depth
assert solution.flat([[[[1]]]], 2) == [[1]]

# n larger than actual depth
assert solution.flat([1, [2, [3, [4]]]], 100) == [1, 2, 3, 4]

# Nested empty arrays
assert solution.flat([[], [[]], [[[]]]], 10) == []

# Mixed nested structure
assert solution.flat(
    [1, [2, [3]], [[4]], 5],
    1
) == [1, 2, [3], [4], 5]

Test	Why
Example 1	Verifies n = 0 behavior
Example 2	Verifies one-level flattening
Example 3	Verifies full flattening
Empty array	Confirms no errors on empty input
No nesting	Ensures integers remain unchanged
Single nested array, n = 0	Tests preservation behavior
Single nested array, n = 1	Tests one-level flattening
Deep nesting with small n	Verifies stopping condition
Very large n	Confirms full flattening when depth is exceeded
Nested empty arrays	Tests handling of empty subarrays
Mixed structure	Verifies selective flattening

Edge Cases

n = 0

This is one of the easiest cases to mishandle because it may be tempting to flatten the first level automatically. However, the condition is strictly less than n. Since the top-level depth is 0, the condition 0 < 0 fails immediately.

The implementation handles this naturally because recursion only occurs when depth < n.

Deeply Nested Arrays

A deeply nested structure such as:

[[[[[1]]]]]

can expose bugs where flattening either goes too far or stops too early.

The implementation correctly tracks the current depth and only recurses while flattening is allowed. Once the depth limit is reached, remaining nested arrays are appended unchanged.

n Larger Than Maximum Depth

Sometimes the requested flatten depth exceeds the actual nesting depth.

For example:

arr = [1, [2, [3]]]
n = 100

A naive implementation might waste effort repeatedly traversing already-flat arrays.

The DFS approach naturally terminates once no nested arrays remain, producing a fully flattened result without unnecessary rescanning.

Empty Nested Arrays

Structures containing empty arrays can be subtle:

[[], [[]], [[[]]]]

Flattening these should not introduce extra values or errors.

The recursive traversal simply iterates through empty lists and contributes nothing to the result, which preserves correctness automatically.