Nested Array Generator - Solution & Explanation

Q: Is Nested Array Generator easy or hard?

Nested Array Generator is considered a medium difficulty problem. The traversal logic is straightforward, but implementing it using generators and handling arbitrary nesting depth requires a good understanding of recursion or stack-based DFS.

Q: Nested Array Generator Python/Java solution

Both Python and JavaScript solutions typically implement a generator that performs depth-first traversal of the nested array. Python uses the `yield` keyword, while JavaScript uses generator functions with `yield` or `yield*` to delegate iteration into nested arrays.

Q: How to solve Nested Array Generator in O(n)?

Traverse the nested array using depth-first search. When encountering an integer, yield it from the generator. When encountering another array, recursively iterate through it or push its elements onto a stack for later processing. Each element is visited once, resulting in O(n) time complexity.

Q: What is the best approach for Nested Array Generator?

The recursive generator approach is usually the cleanest solution. It performs a depth-first traversal of the nested array and yields integers as soon as they are encountered. This method runs in O(n) time and O(d) space, where n is the total number of elements and d is the nesting depth.

Q: Is Nested Array Generator asked at Google/Amazon/Meta?

Problems involving flattening nested structures and implementing iterators or generators appear frequently in interviews at companies like Google, Amazon, and Meta. The exact problem may vary, but the underlying concept of DFS traversal and lazy iteration is commonly tested.

Q: What data structure is used in Nested Array Generator?

The main structures used are recursion stacks or explicit stacks. The recursive solution relies on the call stack to track nested arrays, while the iterative solution uses a stack data structure to simulate depth-first traversal.

Q: What is the time complexity of Nested Array Generator?

The time complexity is O(n) because every integer and nested array element is processed exactly once during traversal. Whether using recursion or a stack-based approach, the algorithm simply walks through the entire nested structure without repeated work.

Medium6 min read

Practice this problem

Problem Statement

Given a multi-dimensional array of integers, return a generator object which yields integers in the same order as inorder traversal.

A multi-dimensional array is a recursive data structure that contains both integers and other multi-dimensional arrays.

inorder traversal iterates over each array from left to right, yielding any integers it encounters or applying inorder traversal to any arrays it encounters.

Example 1:

Input: arr = [[[6]],[1,3],[]]
Output: [6,1,3]
Explanation:
const generator = inorderTraversal(arr);
generator.next().value; // 6
generator.next().value; // 1
generator.next().value; // 3
generator.next().done; // true

Example 2:

Input: arr = []
Output: []
Explanation: There are no integers so the generator doesn't yield anything.

Constraints:

0 <= arr.flat().length <= 10⁵
0 <= arr.flat()[i] <= 10⁵
maxNestingDepth <= 10⁵

Can you solve this without creating a new flattened version of the array?

Approach Overview

Problem Overview: You receive a nested array that may contain integers or other arrays. The task is to build a generator that yields every integer in order, effectively flattening the structure without building a new array in memory.

The challenge is handling arbitrary nesting depth while preserving order. Instead of pre-flattening the structure, the generator should lazily produce values as iteration continues. This pattern is common when working with recursive data structures or tree-like traversal.

Approach 1: Recursive Inorder Traversal (O(n) time, O(d) space)

The most natural solution treats the nested array like a tree. Each array represents a node whose children may be integers or further arrays. Traverse it using recursion. When you encounter an integer, yield it immediately. When you encounter another array, recursively iterate through it using yield* (JavaScript) or nested generator calls. The traversal behaves like a depth-first search where elements are emitted in order. Time complexity is O(n) because every element is visited once, and space complexity is O(d), where d is the maximum nesting depth due to the recursion stack. This approach is clean and concise, especially if you're comfortable with recursion and generator delegation.

Approach 2: Iterative Inorder Traversal Using Stack (O(n) time, O(d) space)

The iterative version removes recursion by maintaining your own stack. Start by pushing the initial array elements onto the stack in reverse order so the leftmost element is processed first. While the stack is not empty, pop the top element. If it is an integer, yield it. If it is another array, push its elements onto the stack again in reverse order. This simulates the same depth-first traversal but avoids function call overhead. Time complexity remains O(n) because each value is processed once. Space complexity is O(d) in the average case for nested depth, though the stack may temporarily hold more elements depending on structure. This pattern is common in problems involving stack-based traversal or iterative depth-first search.

Recommended for interviews: The recursive generator is usually the fastest way to express the idea and demonstrates strong understanding of recursion and lazy iteration. However, interviewers often ask for the iterative stack version as a follow-up to test whether you understand how recursion works internally. Showing both approaches demonstrates solid mastery of traversal patterns.

Approach 1: Recursive Inorder Traversal

The recursive approach leverages the call stack to manage the traversal of the multi-dimensional array. This approach requires defining a function that will be called recursively whenever an array is encountered.

When implementing this recursively, we check if the element is an integer; if so, we yield it. If it is an array, we recursively call the function on this array.

The function inorderTraversal takes a multi-dimensional array arr and iterates over its elements. If an element is an integer, it's directly yielded. If it is a list, the function is called recursively on the sublist, using yield from to yield each item from the resulting generator.

Code

Python JavaScript

Python

JavaScript

Complexity

Time Complexity: O(N), where N is the total number of integers in the arrays since we visit each element once.
Space Complexity: O(D) in the worst case due to recursion, where D is the depth of the nested lists.

Try this approach in the editor →

Approach 2: Iterative Inorder Traversal Using Stack

This method uses a stack to keep track of the state of the array traversal. It mimics the behavior of the call stack in recursion but uses an explicit data structure. We push elements onto the stack in reverse order, and pop them to yield integers or explore more sub-arrays.

The inorderTraversal function initializes a stack with the reversed main array. We pop elements from the stack; if it's an integer, we yield it. If it is a list, its elements are pushed onto the stack in reverse order to maintain the original order while traversing.

Code

Python JavaScript

Python

JavaScript

Complexity

Time Complexity: O(N), where N is the total number of integers in the arrays.
Space Complexity: O(N) due to the use of the stack.

Try this approach in the editor →

Approach 3: Default Approach

Code

TypeScript

Try this approach in the editor →

Complexity Comparison

Approach	Complexity
Recursive Inorder Traversal	Time Complexity: O(N), where N is the total number of integers in the arrays since we visit each element once. Space Complexity: O(D) in the worst case due to recursion, where D is the depth of the nested lists.
Iterative Inorder Traversal Using Stack	Time Complexity: O(N), where N is the total number of integers in the arrays. Space Complexity: O(N) due to the use of the stack.
Default Approach	—

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Recursive Inorder Traversal	O(n)	O(d)	Best for clean generator-based solutions when recursion depth is manageable
Iterative Traversal Using Stack	O(n)	O(d)	Preferred when avoiding recursion or when implementing DFS explicitly

Video Solution

Nested Array Generator - Leetcode 2649 - JavaScript 30-Day Challenge • NeetCodeIO • 7,758 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Nested Array Generator easy or hard?

Nested Array Generator is considered a medium difficulty problem. The traversal logic is straightforward, but implementing it using generators and handling arbitrary nesting depth requires a good understanding of recursion or stack-based DFS.

Nested Array Generator Python/Java solution

Both Python and JavaScript solutions typically implement a generator that performs depth-first traversal of the nested array. Python uses the `yield` keyword, while JavaScript uses generator functions with `yield` or `yield*` to delegate iteration into nested arrays.

How to solve Nested Array Generator in O(n)?

Traverse the nested array using depth-first search. When encountering an integer, yield it from the generator. When encountering another array, recursively iterate through it or push its elements onto a stack for later processing. Each element is visited once, resulting in O(n) time complexity.

What is the best approach for Nested Array Generator?

The recursive generator approach is usually the cleanest solution. It performs a depth-first traversal of the nested array and yields integers as soon as they are encountered. This method runs in O(n) time and O(d) space, where n is the total number of elements and d is the nesting depth.

Is Nested Array Generator asked at Google/Amazon/Meta?

Problems involving flattening nested structures and implementing iterators or generators appear frequently in interviews at companies like Google, Amazon, and Meta. The exact problem may vary, but the underlying concept of DFS traversal and lazy iteration is commonly tested.

What data structure is used in Nested Array Generator?

The main structures used are recursion stacks or explicit stacks. The recursive solution relies on the call stack to track nested arrays, while the iterative solution uses a stack data structure to simulate depth-first traversal.

What is the time complexity of Nested Array Generator?

The time complexity is O(n) because every integer and nested array element is processed exactly once during traversal. Whether using recursion or a stack-based approach, the algorithm simply walks through the entire nested structure without repeated work.

Ready to solve this problem?

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

Practice on FleetCode

Design Cancellable Function

Flatten Deeply Nested Array

Problem Info

DifficultyMedium

Acceptance79.3%

Approaches3

Reading time6 min

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Recursive Inorder Traversal

Code

Complexity

Approach 2: Iterative Inorder Traversal Using Stack

Code

Complexity

Approach 3: Default Approach

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents