Abstract / Summary

Design an iterator to flatten a nested list without using recursion or extra space for storage.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 66% (800k+ submissions).

Typical patterns to solve this problem:

• Depth First Search
• Design
• Iterator
• Queue
• Stack
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a NestedIterator class that enables iteration over a nested list structure where each element may be an integer or another list of similar elements. The iterator flattens the entire nested hierarchy during construction, storing the resulting sequence of integers in a list called data. Subsequent calls to next and hasNext operate on this pre-computed flat list, delivering values in the original left-to-right order.

Flattening Logic

The core of the flattening process resides in the recursive flatten method. It inspects a NestedInteger instance to determine whether it represents a single integer or a list. When an integer is encountered, it is appended directly to the data list. When a list is encountered, the method iterates over each contained NestedInteger and invokes itself recursively, thereby traversing the structure depth-first.

def flatten(self, nested):
    if nested.isInteger():
        self.data.append(nested.getInteger())
    else:
        for n in nested.getList():
            self.flatten(n)

The recursion ensures that arbitrarily deep nesting is handled without requiring explicit stack management by the caller.

Initialization

During object creation, the constructor receives the top-level list of NestedInteger objects. It initializes an empty data list and then iterates over each element of the supplied list, invoking flatten to populate data with all integers in their natural order.

def __init__(self, nestedList: [NestedInteger]):
    self.data = []
    for n in nestedList:
        self.flatten(n)

By performing the flattening once at construction time, the iterator avoids repeated traversal of the nested structure during iteration.

Retrieval

The next method returns the next integer in the sequence by removing the first element of data. This operation maintains the order established during flattening.

def next(self) -> int:
    return self.data.pop(0)

The hasNext method simply checks whether any elements remain in data, indicating whether further calls to next are valid.

def hasNext(self) -> bool:
    return len(self.data) > 0

Together, these methods provide a clean, iterator-like interface that mirrors typical Python iterator protocols.

Edge Cases

The implementation gracefully handles several edge conditions inherent to nested structures. When the input consists solely of integers, the recursion terminates immediately after appending each integer, resulting in a data list that mirrors the input order. If the input contains empty sub-lists, the flatten method iterates over an empty collection, effectively skipping those branches without error. A completely empty top-level list leads to an empty data list, causing hasNext to return False and next to be unreachable, which aligns with expected iterator behavior. Additionally, deeply nested configurations are processed correctly because the recursion naturally descends through each level until reaching integer leaves.

Performance Considerations

A notable optimization is the eager flattening performed during initialization. By converting the entire nested hierarchy into a flat list up front, the iterator eliminates the need for on-the-fly computation during each next call. This design trades a one-time traversal cost for constant-time retrieval of subsequent elements, which is advantageous when many next operations are expected. The use of a simple Python list for data leverages built-in list operations that are highly optimized in CPython. Although pop(0) incurs a shift of remaining elements, the overall impact is mitigated by the fact that the list size diminishes with each call, and the primary cost of flattening has already been incurred. The recursive approach also benefits from Python’s call stack management, allowing the code to handle arbitrarily nested inputs without manual bookkeeping.

Imagine you have a big box filled with lots of other smaller boxes. Some of those smaller boxes have shiny marbles inside, but some of the boxes are actually just more boxes nested inside other boxes. This code is like a helper holding a long flat tray.

The part called init starts the job by looking at everything in the big box. It uses the flatten tool to search through all the layers. When the helper finds a box that has a marble inside, it takes that marble out and places it in a neat line on the tray. If the helper finds another box hidden inside, it keeps looking until it finds the marbles tucked away in the deepest corners.

After all the searching is finished, the tray has a nice row of marbles. The next part allows someone to pick up the marble from the very front of the tray one by one. The hasNext part is like a little checker that looks at the tray to see if there are still any marbles left to give away. If the tray is not empty, the checker says yes, and if it is empty, the checker says no. It is a way of organizing a messy pile of containers so that items can be grabbed in a simple order.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java						TS
	WalkCCC	C++	Python		Java
	leetcode.ca	C++	Python		Java			Go		Rust	TS
	LeetcodeHelp	C++	Python		Java
	MemoryLimitExceeded	C++	Python
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	chenyanzhe	C++
	everthis			JS
	fartem						Ruby
	fengvyi	C++
	fpdjsns	C++
	halfrost							Go
	haoel	C++
	JoshCrozier			JS
	linouk23	C++
	lkwq007		Python
	sonugiri1043	C++
	suxrobGM					C#
	varunu28				Java
	vli02								C
	wisdompeak	C++
	XiaotaoGuo	C++
	YuriSpiridonov		Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
LeetcodeHelp	C++, Java, Python
MemoryLimitExceeded	Python, C++
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
chenyanzhe	C++
everthis	JavaScript
fartem	Ruby
fengvyi	C++
fpdjsns	C++
halfrost	Go
haoel	C++
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
vli02	C
wisdompeak	C++
XiaotaoGuo	C++
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality