Flatten Nested List Iterator LeetCode: Two Approaches to #341

LeetCode 341 — Flatten Nested List Iterator — sits at the intersection of data structures and object-oriented design. Unlike most LeetCode problems that ask you to return a value or array, this one asks you to design an iterator class with two methods: next() and hasNext(). That shift from algorithm to API design is exactly what makes it a favorite at companies like LinkedIn, Google, and Meta.

The flatten nested list iterator LeetCode problem gives you a nested list of integers. Each element is either an integer or another nested list. Your job is to create an iterator that returns every integer in the structure, one at a time, in the order they appear. The challenge is not just correctness — it is how you structure the flattening logic.

In this walkthrough, you will see two approaches: an eager upfront flatten and a lazy stack-based iterator. Both solve the problem, but they reveal fundamentally different design philosophies. Understanding both prepares you not just for LeetCode 341, but for any iterator design question you encounter in interviews.

You are given a nested list where each element is either an integer or a list that itself can contain integers or more nested lists. For example, the input [[1,1],2,[1,1]] means you have a list containing [1,1], then 2, then [1,1]. Your iterator should produce the integers 1, 1, 2, 1, 1 in that order.

The interface requires two methods. hasNext() returns true if there are still integers to return. next() returns the next integer in the flattened sequence. Both methods must work correctly regardless of how deeply nested the input is — a list like [1,[4,[6]]] should produce 1, 4, 6.

What makes this problem tricky is the NestedInteger interface itself. Each element only tells you whether it is an integer (via isInteger()) or a list (via getList()). You cannot index into it like a normal array. This constraint forces you to think about how to peel back layers of nesting without knowing the depth in advance.

The simplest approach is to flatten the entire nested list into a plain array of integers during construction, then iterate over that array. This is the solution most candidates reach first, and it works perfectly.

During initialization, you write a recursive helper that walks the nested list. For each element, if it is an integer you push it to a result array. If it is a list, you recurse into it. After construction finishes, hasNext() checks whether your index has reached the end, and next() returns the value at the current index and increments it.

This approach runs in O(n) time and O(n) space where n is the total number of integers in the structure. The recursion itself uses O(d) stack space where d is the maximum nesting depth, but the flattened array dominates. The downside is that you pay the full cost upfront — even if the caller only needs the first few integers, you have already traversed the entire structure.

The elegant approach — and the one interviewers are usually looking for — uses a stack to flatten the list lazily, one element at a time. Instead of processing everything upfront, you defer the flattening to hasNext() and only peel back nesting when someone actually asks for the next integer.

The idea is straightforward. During construction, you push all elements from the nested list onto a stack in reverse order so the first element sits on top. When hasNext() is called, you peek at the top of the stack. If it is an integer, you return true. If it is a nested list, you pop it, expand its children onto the stack in reverse order, and repeat. This loop continues until either the top is an integer or the stack is empty.

The next() method becomes trivially simple — it just pops the top of the stack and returns its integer value. All the real work happens in hasNext(). This separation of concerns is the key insight: hasNext() is the engine that drives the flattening, and next() is just a consumer.

The space complexity drops to O(d) in the best case, where d is the nesting depth, because you only keep the current path through the structure on the stack. In the worst case — a deeply nested list with many siblings — it can still reach O(n), but for typical inputs the lazy approach uses significantly less memory.

The critical implementation detail is the hasNext() loop. It must handle arbitrarily nested empty lists without crashing or returning incorrect results. The loop structure looks like this: while the stack is not empty and the top element is not an integer, pop the top, get its list, and push each child in reverse order. After the loop, return whether the stack is non-empty.

Reversing the children before pushing is essential. If the nested list is [a, b, c], you must push c first, then b, then a, so that a ends up on top. Forgetting this reversal is the most common implementation bug — the iterator would return elements in the wrong order.

For the next() method, you can safely assume that hasNext() has been called before next(). This is part of the standard iterator contract. That means when next() runs, the top of the stack is guaranteed to be an integer. You pop it, extract the integer value, and return it. No additional checks are needed.

One subtlety: the LeetCode problem uses a NestedInteger interface, not raw arrays. You call isInteger() to check the type, getInteger() to extract the value, and getList() to get the children. In a real interview, clarify whether the interface is mutable and whether getList() returns a copy or a reference — these details matter for correctness.

Edge cases are where candidates lose points on this problem. The most dangerous case is nested empty lists. An input like [[],[]] contains no integers at all. Your hasNext() must correctly return false after expanding these empty lists. If your loop only checks one layer of nesting, it will fail here.

Deeply nested structures like [[[[1]]]] test whether your stack-based approach handles arbitrary depth. Each call to hasNext() should peel back one layer of nesting per iteration of the while loop. With four levels of nesting, hasNext() runs through four iterations before exposing the integer 1 at the top of the stack.

A flat list with no nesting, like [1, 2, 3], should also work without issues. Your constructor pushes 3, 2, 1 onto the stack. Each hasNext() call sees an integer on top immediately and returns true. This is the trivial case but worth testing to make sure your reversal logic does not break on single-element or flat inputs.

Finally, consider a single-element input like [5]. The stack starts with one element. hasNext() sees an integer, returns true. next() pops and returns 5. The next hasNext() call finds an empty stack and returns false. Simple, but make sure your code handles the transition from non-empty to empty gracefully.

LeetCode 341 is more than a coding exercise — it teaches the iterator design pattern, one of the most practical patterns in software engineering. Iterators decouple the traversal logic from the data structure, letting callers consume elements one at a time without knowing how the underlying data is organized. You see this pattern in Java's Iterator interface, Python's __iter__ and __next__ protocols, and JavaScript's Symbol.iterator.

The lazy stack-based solution demonstrates lazy evaluation — the principle of deferring computation until results are actually needed. This is the same idea behind generators in Python, streams in Java 8, and lazy sequences in functional languages. Learning to think lazily is a major upgrade to your problem-solving toolkit.

The flatten nested list iterator leetcode problem also reinforces stack-based iteration as an alternative to recursion. Whenever you have a recursive solution, you can convert it to an iterative one using an explicit stack. This conversion is a core technique that applies to tree traversals, graph DFS, and nested structure processing. Practice it here, and it will click everywhere else.

If you want to solidify these patterns — iterators, lazy evaluation, stack-based traversal — YeetCode flashcards break them into bite-sized prompts you can review daily. Spaced repetition turns understanding into recall, so when you see a design problem in an interview, the approach surfaces automatically.