LeetCode 341: Flatten Nested List Iterator Solution in Python – A Step-by-Step Guide

What Is LeetCode 341: Flatten Nested List Iterator?

In LeetCode 341: Flatten Nested List Iterator, you’re given a nested list where each element is a NestedInteger object (either an integer or a list of NestedInteger objects), and your task is to implement an iterator with two methods: next() to return the next integer, and hasNext() to check if more integers remain. For example, with [[1,1],2,[1,1]], the iterator yields [1,1,2,1,1]. This problem tests your ability to design a lazy traversal, connecting to concepts in LeetCode 339: Nested List Weight Sum.

Problem Statement

• Input: A nested list of NestedInteger objects.
• Output: An iterator class with:
• next(): Returns the next integer.
• hasNext(): Returns True if more integers exist, False otherwise.
• Rules:
• Flatten the list in preorder (left-to-right).
• Use NestedInteger methods: isInteger(), getInteger(), getList().

Constraints

• Number of elements (integers + lists): 1 to 10⁴
• -10⁹ <= integer value <= 10⁹
• Maximum nesting depth: 500

Examples

• Input: [[1,1],2,[1,1]]
• Output: [1,1,2,1,1] (Calls: next() → 1, next() → 1, next() → 2, next() → 1, next() → 1)
• Input: [1,[4,[6]]]
• Output: [1,4,6] (Calls: next() → 1, next() → 4, next() → 6)
• Input: [[]]
• Output: [] (No integers)

Understanding the Problem: Flattening on Demand

To solve LeetCode 341: Flatten Nested List Iterator in Python, we need to design an iterator that flattens a nested list lazily, delivering integers one at a time without precomputing the entire sequence. A naive approach—flattening the list upfront—is O(n) time and space but misses the point of an iterator’s on-demand nature. We’ll use:

• Best Solution (Stack-Based): O(1) amortized time per call, O(d) space—fast and scalable (d = max depth).
• Alternative Solution (Recursive Flattening): O(n) init time, O(n) space—simple but less iterator-like.

Let’s start with the stack-based solution, explained in a beginner-friendly way.

Best Solution: Stack-Based Iterator

Why This Is the Best Solution

The stack-based iterator is the top choice for LeetCode 341 because it’s efficient—O(1) amortized time per next() and hasNext(), O(d) space—and truly lazy, processing only what’s needed for each call. It uses a stack to unwind nested lists on demand, keeping memory usage low. It’s like opening boxes only when you need the next item—smart and sleek!

How It Works

Think of this as a box-opener:

• Step 1: Initialize Stack:
• Push the entire nested list onto the stack (in reverse order for correct traversal).
• Step 2: hasNext():
• Peek at stack top.
• If list, pop and push its elements (reversed).
• If integer, return True; if empty, False.
• Step 3: next():
• Pop and return the top integer (after ensuring hasNext()).
• Step 4: Why It Works:
• Stack unwinds nesting lazily.
• Reverse order ensures left-to-right traversal.

It’s like peeling layers as you go!

Step-by-Step Example

Example: [[1,1],2,[1,1]]

• Init: stack = [[[1,1],2,[1,1]]]
• hasNext():
• Pop [1,1],2,[1,1], push reversed: stack = [[1,1], 2, [1,1]]
• Peek [1,1], pop and push: stack = [1, 1, 2, [1,1]]
• Peek 1 (integer), return True
• next(): Pop 1, return 1, stack = [1, 2, [1,1]]
• hasNext(): Peek 1, return True
• next(): Pop 1, return 1, stack = [2, [1,1]]
• next(): Pop 2, return 2, stack = [[1,1]]
• hasNext(): Pop [1,1], push: stack = [1, 1], return True
• next(): Pop 1, return 1, stack = [1]
• next(): Pop 1, return 1, stack = []
• hasNext(): Empty, return False
• Result: [1, 1, 2, 1, 1]

Code with Detailed Line-by-Line Explanation

Copy codeclass NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        # Initialize stack with reversed nested list
        self.stack = [nestedList[::-1]]

    def next(self) -> int:
        # Ensure hasNext() has prepared an integer
        self.hasNext()
        # Pop and return the top integer
        return self.stack[-1].pop().getInteger()

    def hasNext(self) -> bool:
        # While stack exists and top isn’t an integer
        while self.stack and not self.stack[-1][-1].isInteger():
            # Pop the list and push its elements in reverse
            nested = self.stack.pop().pop()
            self.stack.append(nested.getList()[::-1])
        # Return True if stack has an integer, False if empty
        return len(self.stack) > 0 and self.stack[-1][-1].isInteger()

• Lines 3-4: Init stack with reversed nested list.
• Lines 6-9: next():
• Call hasNext() to ensure integer is ready.
• Pop and return integer from top stack frame.
• Lines 11-17: hasNext():
• Unwind lists until integer or empty.
• Push reversed sublist elements.
• Check if top is integer.
• Time Complexity: O(1) amortized per call—total O(n) across all calls.
• Space Complexity: O(d)—stack depth (d = max nesting depth).

This is like an on-demand unboxer—fast and lean!

Alternative Solution: Recursive Flattening

Why an Alternative Approach?

The recursive flattening approach—O(n) init time, O(n) space—pre-flattens the list into a flat array during initialization, then iterates over it. It’s simpler to implement but uses more space and isn’t truly lazy, making it a baseline for understanding. It’s like unpacking all boxes at once—clear but bulky!

How It Works

Flatten upfront:

• Step 1: Recursively flatten list into array.
• Step 2: Store array and index.
• Step 3: next() and hasNext() use array.

Step-by-Step Example

Example: [1,[4,[6]]]

• Init: Flatten to [1, 4, 6], index = 0
• next(): Return 1, index = 1
• next(): Return 4, index = 2
• next(): Return 6, index = 3
• hasNext(): False (index = len)
• Result: [1, 4, 6]

Code for Recursive Flattening Approach

Copy codeclass NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.flat = []
        def flatten(nested):
            for item in nested:
                if item.isInteger():
                    self.flat.append(item.getInteger())
                else:
                    flatten(item.getList())
        flatten(nestedList)
        self.index = 0

    def next(self) -> int:
        val = self.flat[self.index]
        self.index += 1
        return val

    def hasNext(self) -> bool:
        return self.index < len(self.flat)

• Time Complexity: O(n) init, O(1) per call.
• Space Complexity: O(n)—flat array.

It’s a pre-unpacked iterator—vivid but heavy!

Comparing the Two Solutions

• Stack-Based (Best):
• Pros: O(1) amortized per call, O(d) space, lazy and scalable.
• Cons: Stack logic less intuitive.
• Recursive Flattening (Alternative):
• Pros: O(n) init, O(1) per call, simple structure.
• Cons: O(n) space, not truly lazy.

Stack-based wins for efficiency and design.

Additional Examples and Edge Cases

• [1]: [1].
• [[]]: [].
• [[1,[2]]]: [1, 2].

Both handle these, but stack-based is leaner.

Complexity Breakdown

• Stack-Based: Time O(1) amortized, Space O(d).
• Recursive Flattening: Time O(n) init, Space O(n).

Stack-based is the clear choice.

Key Takeaways

• Stack-Based: Unwind on demand—efficient!
• Recursive Flattening: Flatten first—simple!
• Python: Stacks and recursion shine—see [Python Basics](/python/basics).
• Iterators: Lazy beats eager.

Final Thoughts: Unwrap the List

LeetCode 341: Flatten Nested List Iterator in Python is an iterator design gem. The stack-based solution offers speed and elegance, while recursive flattening provides a tangible baseline. Want more iterator challenges? Try LeetCode 339: Nested List Weight Sum or LeetCode 251: Flatten 2D Vector. Ready to iterate? Head to Solve LeetCode 341 on LeetCode and unwrap those integers today!