Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Flatten Deeply Nested Array solution and explanation

Medium6 min read63.7% acceptanceUpdated 9 Apr 2026
Asked atRivianOtteraiTiktokPayPalGoogleMeta
Practise Flatten Deeply Nested Array
7:09
Flatten Deeply Nested Array - Leetcode 2625 - JavaScript 30-Day ChallengeNeetCodeIO · 7:09 · 11K viewsWatch on YouTube
9 more videos on this problem
  1. Flatten Deeply Nested Array - Leetcode 2625 - JavaScript 30-Day ChallengeNeetCodeIO · 7:09 · 11K views
  2. #day26 |2625. Flatten Deeply Nested Array | 30 Days of JavaScript | Leetcode-2625| 30 Days ChallengeCoding with Ankita · 15:54 · 570 views
  3. JavaScript - Solving 'Flatten Deeply Nested Array' 2625 | Leetcode Challenge 22 of 30 DaysvanAmsen · 4:43 · 413 views
  4. 2625. Flatten Deeply Nested Array - Day 22/30 Leetcode Javascript ChallengeProgramming Live with Larry · 7:09 · 180 views
  5. Flatten Deeply Nested Array - LeetCode 2625 - JavaScript - JS 30 Day Challenge Day 22Alpha-Code · 14:59 · 172 views
  6. 2625. Flatten Deeply Nested Array - Leetcode (Medium). 30 Days of JavaScript | День 26 | Свой flatdev tsx · 2:16 · 65 views
  7. Day 22. LeetCode 2625. Flatten Deeply Nested Array. Daily JS challengeКанал про вирішення ЛітКод Українською · 7:55 · 64 views
  8. Flatten Deeply Nested ArrayDeepak Saini · 14:56 · 40 views
  9. 2625. Flatten Deeply Nested Array | JavaScript Recursion Mastery 🔁CodeCrafting with Vishnu · 12:55 · 33 views
  10. #2625 Flatten Deeply Nested Array | 30 Days of JavaScript | #javascript #leetcodesolution #arrayProgrammers choice · 7:56 · 11 views

The problem

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.

def flatten_array(arr, depth):
    def flatten_helper(subarr, current_depth):
        result = []
        for el in subarr:
            if isinstance(el, list) and current_depth < depth:
                result.extend(flatten_helper(el, current_depth + 1))
            else:
                result.append(el)
        return result
    return flatten_helper(arr, 0)

arr = [1, [2, [3, 4], 5], 6, [7, 8]]
print(flatten_array(arr, 1))
import java.util.ArrayList;
import java.util.List;

public class FlattenArray {
    public static List<Integer> flattenArray(List<Object> arr, int depth) {
        List<Integer> result = new ArrayList<>();
        flattenHelper(arr, depth, 0, result);
        return result;
    }

    private static void flattenHelper(List<Object> arr, int maxDepth, int currentDepth, List<Integer> result) {
        for (Object elem : arr) {
            if (elem instanceof List<?>) {
                if (currentDepth < maxDepth) {
                    flattenHelper((List<Object>) elem, maxDepth, currentDepth + 1, result);
                } else {
                    result.addAll((List<Integer>) elem);
                }
            } else {
                result.add((Integer) elem);
            }
        }
    }

    public static void main(String[] args) {
        List<Object> list = new ArrayList<>();
        list.add(1);
        list.add(2);
        List<Object> sublist = new ArrayList<>();
        sublist.add(3);
        sublist.add(4);
        list.add(sublist);

        List<Integer> flattened = flattenArray(list, 1);
        System.out.println(flattened);
    }
}
#include <iostream>
#include <vector>
using namespace std;

void flattenArrayHelper(vector<int>& result, const vector<int>& arr, int currentDepth, int maxDepth) {
    for (const auto &element : arr) {
        if (currentDepth < maxDepth && typeid(element) == typeid(vector<int>)) {
            flattenArrayHelper(result, element, currentDepth + 1, maxDepth);
        } else {
            result.push_back(element);
        }
    }
}

vector<int> flattenArray(const vector<int>& arr, int maxDepth) {
    vector<int> result;
    flattenArrayHelper(result, arr, 0, maxDepth);
    return result;
}

int main() {
    vector<int> arr = {1, 2, 3, 4};
    vector<int> flattened = flattenArray(arr, 1);
    for (int num : flattened) {
        cout << num << " ";
    }
    return 0;
}
function flattenArray(arr, maxDepth) {
    function flattenHelper(subarr, currentDepth) {
        let result = [];
        for (let el of subarr) {
            if (Array.isArray(el) && currentDepth < maxDepth) {
                result = result.concat(flattenHelper(el, currentDepth + 1));
            } else {
                result.push(el);
            }
        }
        return result;
    }

    return flattenHelper(arr, 0);
}

let arr = [1, [2, [3, 4], 5], 6, [7, 8]];
console.log(flattenArray(arr, 1));
#include <stdio.h>
#include <stdlib.h>

void flattenArrayHelper(int** result, int* resultSize, int* arr, int arrSize, int currentDepth, int maxDepth) {
    for (int i = 0; i < arrSize; i++) {
        if (currentDepth < maxDepth && arr[i] == -1) { // Mock condition for subarrays
            int subArray[] = {arr[i + 1], arr[i + 2]};
            flattenArrayHelper(result, resultSize, subArray, 2, currentDepth + 1, maxDepth);
            i += 2; // Assuming subarray length fixed for mock-up
        } else {
            (*result)[(*resultSize)++] = arr[i];
        }
    }
}

int* flattenArray(int* arr, int arrSize, int maxDepth, int* returnSize) {
    int* result = (int*)malloc(arrSize * sizeof(int));
    *returnSize = 0;
    flattenArrayHelper(&result, returnSize, arr, arrSize, 0, maxDepth);
    return result;
}

int main() {
    int arr[] = {1, 2, -1, 4, 5, 3}; // Mock representation
    int returnSize;
    int* flattened = flattenArray(arr, 6, 1, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", flattened[i]);
    }
    free(flattened);
    return 0;
}
using System;
using System.Collections.Generic;

class FlattenArray {
    public static List<int> Flatten(List<object> arr, int maxDepth) {
        List<int> result = new List<int>();
        FlattenHelper(arr, maxDepth, 0, result);
        return result;
    }

    private static void FlattenHelper(List<object> arr, int maxDepth, int currentDepth, List<int> result) {
        foreach (var element in arr) {
            if (element is List<object> sublist) {
                if (currentDepth < maxDepth)
                    FlattenHelper(sublist, maxDepth, currentDepth + 1, result);
                else
                    result.AddRange((List<int>)sublist);
            } else {
                result.Add((int)element);
            }
        }
    }

    static void Main() {
        var arr = new List<object> { 1, 2, new List<object> { 3, 4 }, 5 };
        var flattened = Flatten(arr, 1);
        Console.WriteLine(string.Join(", ", flattened));
    }
}

This Python code employs recursion with a helper function flatten_helper that tracks the depth of processing. If the current depth is less than the specified depth, it flattens the array; otherwise, it copies the subarray intact. The main function flatten_array initializes this recursive process.

Complexity

Time Complexity: O(m) where m is the size of all elements at all levels.
Space Complexity: O(m) considering stack depth and aggregated results.

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.

def flatten_array(arr, n):
    stack = [(arr, 0)]
    result = []
    
    while stack:
        curr, depth = stack.pop()
        i = 0
        while i < len(curr):
            if isinstance(curr[i], list):
                if depth < n:
                    stack.append((curr, i + 1))
                    stack.append((curr[i], depth + 1))
                    break
                else:
                    result.extend(curr[i])
            else:
                result.append(curr[i])
            i += 1
    return result

# Example usage:
arr = [1, [2, [3, 4], 5], 6, [7, 8]]
print(flatten_array(arr, 1))
import java.util.*;

public class FlattenArray {
    private static class Element {
        List<Object> list;
        int index;
        int depth;

        Element(List<Object> list, int depth) {
            this.list = list;
            this.index = 0;
            this.depth = depth;
        }
    }

    public static List<Integer> flattenArray(List<Object> arr, int n) {
        List<Integer> result = new ArrayList<>();
        Stack<Element> stack = new Stack<>();
        stack.push(new Element(arr, 0));

        while (!stack.isEmpty()) {
            Element current = stack.peek();
            if (current.index >= current.list.size()) {
                stack.pop();
            } else {
                Object item = current.list.get(current.index++);
                if (item instanceof List) {
                    if (current.depth < n) {
                        stack.push(new Element((List<Object>) item, current.depth + 1));
                    } else {
                        result.addAll((List<Integer>) item);
                    }
                } else {
                    result.add((Integer) item);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        List<Object> arr = Arrays.asList(1, 2, Arrays.asList(3, 4));
        List<Integer> flattened = flattenArray(arr, 1);
        System.out.println(flattened);
    }
}
// This C++ code uses a stack-based iterative approach. 
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> flattenArray(const vector<int>& arr, int depth) {
    vector<int> flat;
    stack<pair<const vector<int>*, int>> stk;
    stk.push({&arr, 0});

    while (!stk.empty()) {
        const vector<int>* sub_vec = stk.top().first;
        int i = stk.top().second;
        stk.pop();

        while (i < sub_vec->size()) {
            const auto& el = (*sub_vec)[i++];
            if (el == -1) { // Assuming a condition indicates subarrays
                vector<int> mockSub{7, 8};
                if (depth > 0) {
                    stk.push({sub_vec, i});
                    stk.push({&mockSub, 0});
                    break;
                }
            } else {
                flat.push_back(el);
            }
        }
    }

    return flat;
}

int main() {
    vector<int> arr = {1, 2, -1, 3}; // Simplified representation
    vector<int> result = flattenArray(arr, 1);
    for (int x : result) cout << x << " ";
    return 0;
}
function flattenArray(arr, maxDepth) {
    const result = [];
    const stack = [{ arr, index: 0, depth: 0 }];

    while (stack.length > 0) {
        const { arr: current, index, depth } = stack.pop();

        if (index < current.length) {
            if (Array.isArray(current[index]) && depth < maxDepth) {
                stack.push({ arr: current, index: index + 1, depth });
                stack.push({ arr: current[index], index: 0, depth: depth + 1 });
            } else {
                result.push(current[index]);
                stack.push({ arr: current, index: index + 1, depth });
            }
        }
    }

    return result;
}

let arr = [1, [2, [3, 4], 5], 6, [7, 8]];
console.log(flattenArray(arr, 1));
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

struct Element {
    int* data;
    int size;
    int index;
    int depth;
};

void push(struct Element* stack, int* top, int* data, int size, int depth) {
    stack[(*top)++] = (struct Element){ data, size, 0, depth};
}

int* flattenArray(int* arr, int arrSize, int n, int* returnSize) {
    int* result = (int*)malloc(arrSize * sizeof(int));
    int resultIndex = 0;
    struct Element stack[1000];
    int top = 0;
    push(stack, &top, arr, arrSize, 0);

    while (top > 0) {
        struct Element* current = &stack[top-1];

        if (current->index >= current->size) {
            top--;
            continue;
        }
        int value = current->data[current->index++];
        
        // Check if the current value is a marker for a nested array
        if (value == -1) { // Assume this is to mock subarray occurrence
            int subArray[] = {3, 4}; // Mock subarray
            if (current->depth < n) {
                push(stack, &top, subArray, 2, current->depth + 1);
            } else {
                result[resultIndex++] = value; // Keep the entire subArray as is
            }
            continue;
        }
        result[resultIndex++] = value;
    }

    *returnSize = resultIndex;
    return result;
}

int main() {
    int arr[] = {1, -1, 2, 3}; // Mock
    int returnSize;
    int* flattened = flattenArray(arr, 4, 1, &returnSize);
    for (int i = 0; i < returnSize; i++) {
        printf("%d ", flattened[i]);
    }
    free(flattened);
    return 0;
}
using System;
using System.Collections;
using System.Collections.Generic;

class FlattenArray {
    public static List<int> Flatten(IList arr, int n) {
        Stack<Tuple<IList, int>> stack = new Stack<Tuple<IList, int>>();
        List<int> result = new List<int>();
        stack.Push(new Tuple<IList, int>(arr, 0));

        while (stack.Count > 0) {
            var (current, depth) = stack.Pop();
            for (int i = 0; i < current.Count; i++) {
                if (current[i] is IList sublist) {
                    if (depth < n) {
                        stack.Push(new Tuple<IList, int>(current, i + 1));
                        stack.Push(new Tuple<IList, int>(sublist, depth + 1));
                        break;
                    } else {
                        result.AddRange((IList<int>)sublist);
                    }
                } else {
                    result.Add((int)current[i]);
                }
            }
        }

        return result;
    }

    static void Main() {
        IList arr = new List<object> { 1, 2, new List<object> { 3, 4 }, 5 };
        var flattened = Flatten(arr, 1);
        Console.WriteLine(string.Join(", ", flattened));
    }
}

Python’s stack-based solution iterates over the input list using a manual stack. Given tuples holding both the current list and index, flatten_array() evaluates depth to determine their inclusion, breaking into subarrays where appropriate.

Complexity

Time Complexity: O(m), by processing entire depth. Space Complexity: O(m), from stack management and overall flattened result store.

Try this approach in the editor

Approach 3: Default Approach

type MultiDimensionalArray = (number | MultiDimensionalArray)[];

var flat = function (arr: MultiDimensionalArray, n: number): MultiDimensionalArray {
    if (!n) {
        return arr;
    }
    const ans: MultiDimensionalArray = [];
    for (const x of arr) {
        if (Array.isArray(x) && n) {
            ans.push(...flat(x, n - 1));
        } else {
            ans.push(x);
        }
    }
    return ans;
};
Try this approach in the editor

Complexity comparison

ApproachComplexity
Recursive Flattening up to Depth

Time Complexity: O(m) where m is the size of all elements at all levels.
Space Complexity: O(m) considering stack depth and aggregated results.

Iterative Flattening with Depth Control

Time Complexity: O(m), by processing entire depth. Space Complexity: O(m), from stack management and overall flattened result store.

Default Approach–

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

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.

Comments

Next problem · similarJSON Deep EqualMedium
Now write it yourselfClose this page and solve Flatten Deeply Nested Array in the editor, without looking.
Practise Flatten Deeply Nested Array