Skip to main content
Talentd

Flatten Deeply Nested Array - Solution & Explanation

Medium15 min readAsked at: Meta, PayPal, Google +3
Practice this problem

Problem Statement

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 <= 105
  • 0 <= count of subarrays in arr <= 105
  • maxDepth <= 1000
  • -1000 <= each number <= 1000
  • 0 <= n <= 1000

Approach Overview

Problem Overview: You receive an array that may contain integers or other arrays nested at multiple levels. The task is to flatten the structure up to a given depth n. Elements deeper than n levels must remain nested, while everything within that depth becomes part of a single array.

Approach 1: Recursive Flattening up to Depth (Time: O(n), Space: O(n))

This approach directly mirrors the nested structure using recursion. Iterate through the array and check each element. If the element is an array and the remaining depth is greater than zero, recursively flatten that subarray with depth - 1. Otherwise, append the element to the result. Every element is visited once, which gives an overall O(n) time complexity where n is the total number of elements across all nested arrays. The recursion stack may grow up to the maximum nesting level, resulting in O(n) auxiliary space in the worst case.

This method is clean and intuitive. The recursive calls naturally handle nested structures without additional data structures. If you're comfortable with recursion, this solution is usually the fastest to implement during interviews.

Approach 2: Iterative Flattening with Depth Control (Time: O(n), Space: O(n))

The iterative approach replaces the recursion stack with an explicit stack or queue. Iterate through the array while tracking the remaining flatten depth for each element. When encountering a nested array and the allowed depth is still positive, push its contents back into the stack with depth - 1. Otherwise, append the element to the output array. This simulates the recursive traversal but avoids function call overhead.

Each element is still processed once, so the time complexity remains O(n). The explicit stack may temporarily store elements from nested arrays, leading to O(n) space in the worst case. This method relies on a classic stack-based traversal of nested structures and works well when recursion depth might become large.

Since the problem fundamentally deals with nested list traversal, both solutions rely heavily on understanding arrays and hierarchical structures.

Recommended for interviews: The recursive approach is usually expected first because it directly models the nested structure and is easy to reason about. Interviewers often accept it as the primary solution. The iterative stack-based approach demonstrates deeper control over traversal mechanics and avoids recursion limits, which can be valuable when discussing scalability or language stack constraints.

Approach 1: Recursive Flattening up to Depth

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.

This C solution uses mock conditions/flags to illustrate how you might handle subarray occurrences in a real scenario where int arrays don't inherently distinguish subarrays. A recursive helper function processes elements while managing the depth level. This mock example assumes a simple subarray flag (-1) just for demonstration purposes.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Iterative Flattening with Depth Control

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.

This iterative C solution uses a stack to manage array processing, avoiding direct recursion. This mock setup involves using markers and demonstrates how such a stack could work for real subarrays. It pushes all values and sub-arrays into a custom stack, managing the depth manually.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m), iterating through each array element.
Space Complexity: O(m) due to storage in stack elements.

Try this approach in the editor →

Approach 3: Default Approach

Code

TypeScript

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Recursive Flattening up to Depth

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.

Iterative Flattening with Depth Control

Time Complexity: O(m), iterating through each array element.
Space Complexity: O(m) due to storage in stack elements.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Flattening up to DepthO(n)O(n)Best when recursion depth is manageable and you want the simplest implementation
Iterative Flattening with StackO(n)O(n)Useful when avoiding recursion limits or when explicit control over traversal is preferred

Video Solution

Flatten Deeply Nested Array - Leetcode 2625 - JavaScript 30-Day Challenge • NeetCodeIO • 11,424 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Flatten Deeply Nested Array easy or hard?
Flatten Deeply Nested Array is generally considered a medium difficulty problem. The logic is straightforward once you recognize that recursion or a stack can traverse nested structures, but managing the depth constraint correctly requires careful implementation.
Flatten Deeply Nested Array Python/Java solution
In Python or Java, the solution usually uses recursion or a stack-based loop. The recursive method iterates through the array and calls itself on nested arrays while decreasing the depth parameter. Both languages can implement the solution with O(n) time complexity.
How to solve Flatten Deeply Nested Array in O(n)?
Traverse the array and flatten subarrays only when the remaining depth is greater than zero. Use recursion or an explicit stack to process nested arrays while decrementing the depth. Since every element is processed exactly once, the overall complexity remains O(n).
What is the best approach for Flatten Deeply Nested Array?
Recursive flattening with a depth parameter is typically the best approach. It naturally matches the nested structure of the input and processes each element once. The algorithm runs in O(n) time and uses O(n) space due to the recursion stack and result array.
Is Flatten Deeply Nested Array asked at Google/Amazon/Meta?
Nested array traversal problems appear in interviews at large tech companies including Google, Amazon, and Meta. Variations of flattening nested lists or arrays are common because they test recursion, stack usage, and understanding of hierarchical data structures.
What data structure is used in Flatten Deeply Nested Array?
The main data structures used are arrays for storing results and either a recursion call stack or an explicit stack for traversal. These structures help manage nested elements while tracking how much flattening depth remains.
What is the time complexity of Flatten Deeply Nested Array?
The time complexity is O(n), where n is the total number of elements across all nested arrays. Each value or subarray is visited once during traversal, whether using recursion or an iterative stack-based method.

Ready to solve this problem?

Practice Flatten Deeply Nested Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Convert Object to JSON String

Next

JSON Deep Equal