NUHMAN.com

Introduction

In LeetCode 341: Flatten Nested List Iterator, you're tasked with designing an iterator to flatten a deeply nested list of integers. The goal is to seamlessly iterate through all integers, as if the list were flat, using the typical iterator interface (hasNext and next).

This problem merges data structure design with recursion and is a great example of implementing custom iterators.

Problem Statement

You are given a nested list of integers nestedList. Each element is either an integer or a list. Implement an iterator that flattens the list such that you can iterate over all the integers sequentially using:

• next() – returns the next integer in the nested structure.
• hasNext() – returns True if there are more integers to return.

Example

python

Input: nestedList = [[1,1],2,[1,1]]
Output: [1,1,2,1,1]

Operations:
i, v = NestedIterator(nestedList), []
while i.hasNext(): v.append(i.next())

🧠 Key Idea

• Recursive Preprocessing Approach:
• Flatten the nested structure into a simple list of integers once at the beginning.
• Use a pointer to iterate through that list.
• Alternative: Lazy evaluation using a stack, which we'll cover after.

✅ Python Code – Preprocessing with DFS

python

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.flat_list = []
        self.index = 0
        self.flatten(nestedList)

    def flatten(self, nestedList):
        for item in nestedList:
            if item.isInteger():
                self.flat_list.append(item.getInteger())
            else:
                self.flatten(item.getList())

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

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

🔍 Step-by-Step Breakdown

Given: nestedList = [[1, [4, [6]]], 2]

1. Start DFS:

• Enter outer list → [1, [4, [6]]] and 2

1. Dive into [1, [4, [6]]]:

• 1 → append
• [4, [6]] → dive again
• 4 → append
• [6] → dive again → 6 → append

1. Append 2

Resulting flat list: [1, 4, 6, 2]

⏱️ Complexity Analysis

MetricValueTime ComplexityO(n)Space ComplexityO(n)

Where n is the total number of integers in the nested list (excluding nested brackets). This is due to recursive flattening into a new list.

🔄 Alternative: Lazy Evaluation Using Stack

python

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = nestedList[::-1]

    def next(self) -> int:
        return self.stack.pop().getInteger()

    def hasNext(self) -> bool:
        while self.stack:
            top = self.stack[-1]
            if top.isInteger():
                return True
            self.stack.pop()
            self.stack.extend(top.getList()[::-1])
        return False

This version avoids pre-flattening the whole structure and only flattens as needed (on demand).

🔧 Use Case Scenarios

• Parsing nested JSON/XML
• File system crawlers
• Multi-level UI rendering (menus, components)

✅ Conclusion

LeetCode 341: Flatten Nested List Iterator is a great example of recursion meets design patterns. It’s a powerful way to build your understanding of iterators, custom data structures, and flattening algorithms.

Whether you choose the pre-flattening approach or the lazy stack-based one, both are efficient and acceptable depending on your use case.