Flatten Nested List Iterator: Iterator แปลง Nested List เป็น Flat

โจทย์

กำหนด Nested List ของจำนวนเต็ม (แต่ละ element เป็น int หรือ list) สร้าง Iterator ที่ flatten ทุกอย่าง

ตัวอย่าง: [[1,1],2,[1,1]] → Iterator ให้ 1, 1, 2, 1, 1

วิธีแก้: Pre-flatten ใน Constructor (Eager)

ใช้ DFS recursive แปลง nested list ทั้งหมดเป็น flat list ตอน init แล้ว iterator แค่เดิน index

การติดตั้ง (Python Implementation)

class NestedIterator:
    def __init__(self, nestedList: list):
        self.flat = []
        self.index = 0
        self._flatten(nestedList)
    
    def _flatten(self, nested_list):
        for item in nested_list:
            if isinstance(item, int):
                self.flat.append(item)
            else:
                self._flatten(item)  # recursive
    
    def next(self) -> int:
        val = self.flat[self.index]
        self.index += 1
        return val
    
    def hasNext(self) -> bool:
        return self.index < len(self.flat)

# ทดสอบ
nested = [[1,1], 2, [1,1]]
it = NestedIterator(nested)
while it.hasNext():
    print(it.next(), end=' ')  # 1 1 2 1 1
print()

# Nested ลึกกว่า
nested2 = [1, [4, [6]]]
it2 = NestedIterator(nested2)
while it2.hasNext():
    print(it2.next(), end=' ')  # 1 4 6

Output

1 1 2 1 1
1 4 6

Alternative: Lazy Flattening (Stack-based)

ไม่ flatten ทั้งหมดตอน init ใช้ stack เก็บ iterator ระหว่างการทำงาน (memory efficient สำหรับ huge nested lists)

class NestedIteratorLazy:
    def __init__(self, nestedList):
        # Stack of iterators
        self.stack = [iter(nestedList)]
        self.next_val = None
    
    def next(self):
        if self.next_val is None:
            self.hasNext()
        val = self.next_val
        self.next_val = None
        return val
    
    def hasNext(self):
        if self.next_val is not None:
            return True
        
        while self.stack:
            try:
                item = next(self.stack[-1])
                if isinstance(item, int):
                    self.next_val = item
                    return True
                else:
                    self.stack.append(iter(item))
            except StopIteration:
                self.stack.pop()
        return False

Complexity (Eager Version)

• Constructor: O(N) time, O(N) space (N = total integers)
• next(): O(1)
• hasNext(): O(1)

Complexity (Lazy Version)

• Constructor: O(1)
• next()/hasNext(): Amortized O(1)
• Space: O(D) โดย D = maximum nesting depth

สรุป

Flatten Nested List Iterator มี 2 แนวทาง: Eager (pre-flatten, เรียบง่าย เร็ว) และ Lazy (stack-based, memory efficient) เลือกตาม use case

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ