LeetCode 2649 - Nested Array Generator

This problem asks us to implement a generator that traverses a multi-dimensional array and yields integers in the same order as an inorder traversal. The input is not a normal one-dimensional list.

leetcodemedium

LeetCode Problem 2649

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

This problem asks us to implement a generator that traverses a multi-dimensional array and yields integers in the same order as an inorder traversal.

The input is not a normal one-dimensional list. Instead, it is a recursive structure where each element may either be:

  • An integer
  • Another multi-dimensional array containing more integers or nested arrays

Our task is to return a generator object that produces integers one at a time, preserving the same order we would encounter them if we recursively traversed the structure from left to right.

For example, consider:

[[[6]],[1,3],[]]

The traversal works as follows:

  1. Visit [[6]]
  2. Visit [6]
  3. Yield 6
  4. Visit [1,3]
  5. Yield 1
  6. Yield 3
  7. Visit [], nothing to yield

The final output order becomes:

[6,1,3]

A key detail is that we are required to return a generator, not a fully flattened array. This means values should be produced lazily, only when requested with next(), instead of computing everything upfront.

The constraints are important:

  • arr.flat().length <= 10^5
  • maxNestingDepth <= 10^5

These values indicate the input may be extremely large and deeply nested.

A naive recursive solution can fail because Python recursion depth is limited, and deeply nested arrays may cause a stack overflow. Similarly, creating a completely flattened version of the array violates the follow-up requirement and wastes memory.

Several edge cases matter immediately:

  • An empty input array [], where nothing should be yielded.
  • Nested empty arrays such as [[], [[]], []], which contain no integers.
  • Extremely deep nesting like [[[[[[5]]]]]], which may break recursive implementations.
  • Mixed nesting structures such as [1,[2,[3]],4], where integers appear at multiple depths.
  • Large inputs with up to 10^5 elements, where unnecessary copying becomes expensive.

The problem guarantees that all leaf elements are integers, so we do not need to validate input types beyond checking whether something is a list or an integer.

Approaches

Brute Force Approach

The most straightforward solution is to first flatten the entire array into a new list and then yield elements from that list.

We could recursively traverse the structure, append every integer into a result array, and finally iterate over the flattened list using a generator.

This works because recursive traversal naturally preserves the required left-to-right ordering. Every nested array is explored before continuing to the next sibling element.

However, this approach has major drawbacks.

First, it violates the follow-up requirement asking us to avoid creating a new flattened version of the array.

Second, it requires extra memory proportional to the number of integers in the structure. Since the flattened size may reach 10^5, storing everything upfront is unnecessary.

Third, recursion becomes dangerous because nesting depth can also reach 10^5, which can exceed recursion limits and crash.

Optimal Approach

The key insight is that we do not need to flatten the array first. Since generators already support lazy evaluation, we can yield integers as soon as we encounter them.

Instead of recursion, we use an explicit stack to simulate traversal iteratively. This avoids recursion depth problems and allows us to process arbitrarily deep nesting safely.

The idea is to maintain a stack of iterators or positions that represent where we currently are in the nested structure.

Whenever we encounter:

  • An integer, we yield it immediately.
  • A nested array, we push it onto the stack and continue exploring it.

This preserves left-to-right traversal order while using only the necessary memory for the traversal state.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Fully flattens the array before yielding
Optimal O(n) O(d) Iterative traversal using a stack, where d is nesting depth

Here, n is the total number of integers and nested array elements visited, while d is the maximum nesting depth.

Algorithm Walkthrough

We use an iterative depth-first traversal with a stack.

  1. Initialize a stack with the input array iterator.

The stack represents our traversal state. Each entry keeps track of which array we are currently exploring. 2. While the stack is not empty, examine the top iterator.

The top of the stack always represents the current array being traversed. 3. Try to get the next element from the current iterator.

If there are no remaining elements, remove this iterator from the stack because that array has been completely processed. 4. If the next element is an integer, yield it immediately.

Since generators are lazy, we do not store the number anywhere. We return it as soon as we encounter it. 5. If the next element is another array, push its iterator onto the stack.

This ensures nested arrays are processed before continuing with remaining siblings, preserving correct left-to-right traversal order. 6. Continue until the stack becomes empty.

At this point, every nested structure has been fully explored.

Why it works

The algorithm maintains an important invariant:

The stack always represents the exact traversal path from the root to the current position.

Whenever a nested array is encountered, it is pushed onto the stack and explored completely before returning to the parent array. This mimics recursive depth-first traversal exactly, ensuring integers are yielded in the same left-to-right inorder sequence.

Because every element is visited exactly once, the traversal is both correct and efficient.

Python Solution

from typing import List, Generator, Union

class Solution:
    def inorderTraversal(
        self, arr: List[Union[int, list]]
    ) -> Generator[int, None, None]:

        stack = [iter(arr)]

        while stack:
            try:
                value = next(stack[-1])

                if isinstance(value, int):
                    yield value
                else:
                    stack.append(iter(value))

            except StopIteration:
                stack.pop()

The implementation begins by initializing a stack containing an iterator over the input array.

Instead of recursively traversing nested lists, we repeatedly process the iterator at the top of the stack.

Inside the loop, we attempt to retrieve the next value from the current iterator. If successful, we inspect the value.

If the value is an integer, we immediately yield it. This satisfies the lazy behavior required by the problem.

If the value is another array, we create an iterator for that array and push it onto the stack. This ensures nested arrays are fully explored before continuing with remaining sibling elements.

If a StopIteration exception occurs, it means the current array has been fully processed, so we remove that iterator from the stack.

This iterative approach avoids recursion entirely, making it safe for deeply nested inputs up to the problem constraints.

Go Solution

type NestedArray []interface{}

func inorderTraversal(arr NestedArray) chan int {
	result := make(chan int)

	go func() {
		defer close(result)

		stack := []struct {
			array NestedArray
			index int
		}{
			{array: arr, index: 0},
		}

		for len(stack) > 0 {
			top := &stack[len(stack)-1]

			if top.index >= len(top.array) {
				stack = stack[:len(stack)-1]
				continue
			}

			value := top.array[top.index]
			top.index++

			switch v := value.(type) {
			case int:
				result <- v
			case NestedArray:
				stack = append(stack, struct {
					array NestedArray
					index int
				}{
					array: v,
					index: 0,
				})
			case []interface{}:
				stack = append(stack, struct {
					array NestedArray
					index int
				}{
					array: NestedArray(v),
					index: 0,
				})
			}
		}
	}()

	return result
}

The Go implementation uses a channel to simulate generator behavior because Go does not have native generators.

Instead of iterators, we explicitly store:

  • The current array
  • The current index within that array

Each stack entry tracks traversal progress for one nesting level.

When an integer is encountered, it is sent through the channel. When a nested array is found, a new stack frame is pushed.

Go-specific considerations include handling type assertions using interface{} and explicitly managing indices because Go slices do not have iterator objects like Python. Empty slices naturally work without special handling.

Worked Examples

Example 1

Input

[[[6]],[1,3],[]]

Initial stack:

[ iterator([[[6]],[1,3],[]]) ]
Step Current Value Action Yielded Stack State
1 [[6]] Push iterator - root, [[6]]
2 [6] Push iterator - root, [[6]], [6]
3 6 Yield integer 6 unchanged
4 exhausted Pop - root, [[6]]
5 exhausted Pop - root
6 [1,3] Push iterator - root, [1,3]
7 1 Yield integer 1 unchanged
8 3 Yield integer 3 unchanged
9 exhausted Pop - root
10 [] Push iterator - root, []
11 exhausted Pop - root
12 exhausted Pop - empty

Final output:

[6,1,3]

Example 2

Input

[]

Initial stack:

[ iterator([]) ]
Step Action Stack
1 Iterator exhausted Pop
2 Stack empty Stop

Final output:

[]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every element is visited exactly once
Space O(d) Stack stores only the current nesting path

The algorithm processes every integer and nested array exactly one time, leading to linear time complexity.

The auxiliary space comes only from the traversal stack. At worst, the stack size equals the maximum nesting depth, which is d. Unlike flattening, we never allocate space proportional to the total number of integers.

Test Cases

from typing import List, Union

class Solution:
    def inorderTraversal(self, arr):
        stack = [iter(arr)]

        while stack:
            try:
                value = next(stack[-1])

                if isinstance(value, int):
                    yield value
                else:
                    stack.append(iter(value))

            except StopIteration:
                stack.pop()

sol = Solution()

# Example 1
assert list(sol.inorderTraversal([[[6]], [1, 3], []])) == [6, 1, 3]  # nested traversal

# Example 2
assert list(sol.inorderTraversal([])) == []  # empty input

# Single integer
assert list(sol.inorderTraversal([5])) == [5]  # one value

# Deep nesting
assert list(sol.inorderTraversal([[[[[5]]]]])) == [5]  # deeply nested single element

# Mixed nesting
assert list(sol.inorderTraversal([1, [2, [3]], 4])) == [1, 2, 3, 4]  # mixed structure

# Empty nested arrays
assert list(sol.inorderTraversal([[], [[]], []])) == []  # nested empties

# Multiple sibling arrays
assert list(sol.inorderTraversal([[1, 2], [3], [4, 5]])) == [1, 2, 3, 4, 5]  # siblings

# Large flat array
assert list(sol.inorderTraversal([1, 2, 3, 4, 5])) == [1, 2, 3, 4, 5]  # no nesting

# Complex nesting
assert list(sol.inorderTraversal([[1, [2]], [], [[3, [4]]], 5])) == [1, 2, 3, 4, 5]  # mixed deep nesting
Test Why
[[[6]], [1,3], []] Verifies provided example and nested traversal
[] Confirms empty input works
[5] Tests simplest non-empty case
[[[[[5]]]]] Validates deep nesting
[1,[2,[3]],4] Ensures correct left-to-right order
[[],[[]],[]] Confirms empty nested arrays produce no output
[[1,2],[3],[4,5]] Tests multiple sibling subarrays
[1,2,3,4,5] Verifies flat arrays work correctly
[[1,[2]],[],[[3,[4]]],5] Stresses mixed nesting and empties

Edge Cases

Empty Input Array

An empty array such as [] contains no integers to yield. A naive implementation might accidentally fail if it assumes at least one element exists.

This implementation handles the case naturally. The iterator immediately raises StopIteration, causing the stack to be popped and traversal to end without yielding anything.

Deeply Nested Arrays

Inputs like:

[[[[[[5]]]]]]

can easily exceed recursion depth limits if implemented recursively.

Our iterative stack-based solution completely avoids recursion. Since it explicitly manages traversal state with a stack, it safely supports nesting depths up to 10^5.

Nested Empty Arrays

Structures such as:

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

contain many arrays but no integers.

A buggy solution may accidentally yield incorrect values or fail while descending into empty arrays. Here, empty iterators simply finish immediately and are removed from the stack, ensuring no unnecessary work and no incorrect output.

Mixed Integers and Nested Arrays

Inputs like:

[1, [2, [3]], 4]

require maintaining strict left-to-right order across different nesting levels.

The stack guarantees nested arrays are fully explored before resuming the parent array, preserving the exact traversal order required by the problem.