NUHMAN.com

Introduction

LeetCode 281: Zigzag Iterator is a fun design problem that asks you to build an iterator that returns elements from two input lists in an alternating (zigzag) fashion.

This tests your grasp on:

• Iterator design patterns
• Queue management
• Handling unequal lengths gracefully

Problem Statement

Given two vectors (lists), implement an iterator to return their elements alternatingly.

If one list is longer, the remaining elements should be returned after the shorter one is exhausted.

Example

python

Input:
v1 = [1, 2]
v2 = [3, 4, 5, 6]

Output:
[1, 3, 2, 4, 5, 6]

✅ Step-by-Step Solution

🧠 Key Idea

To iterate in a zigzag way, we need to:

• Alternate pulling from each list
• Skip lists that are empty

We can do this efficiently using a queue of iterators (or indices), ensuring that:

1. If the current iterator has elements, we pull one and rotate it to the back.
2. If not, we discard it.

✅ Python Code Using Queue of Iterators

python

from collections import deque

class ZigzagIterator:
    def __init__(self, v1: list[int], v2: list[int]):
        self.queue = deque()
        if v1:
            self.queue.append(iter(v1))
        if v2:
            self.queue.append(iter(v2))

    def next(self) -> int:
        if self.hasNext():
            curr_iter = self.queue.popleft()
            val = next(curr_iter)
            if any(True for _ in [curr_iter]):
                self.queue.append(curr_iter)
            return val

    def hasNext(self) -> bool:
        return bool(self.queue)

🧪 Dry Run Example

v1 = [1, 2], v2 = [3, 4, 5, 6]

1. Pop v1 → output 1 → append v1 back
2. Pop v2 → output 3 → append v2 back
3. Pop v1 → output 2 → no more → don’t append
4. Pop v2 → output 4 → append
5. Pop v2 → output 5 → append
6. Pop v2 → output 6 → end

✅ Output: [1, 3, 2, 4, 5, 6]

🔁 Alternate Version: Use Index Tracking (if not using iterators)

python

class ZigzagIterator:
    def __init__(self, v1: list[int], v2: list[int]):
        self.data = [(v1, 0), (v2, 0)]

    def next(self) -> int:
        for _ in range(len(self.data)):
            v, idx = self.data.pop(0)
            if idx < len(v):
                self.data.append((v, idx + 1))
                return v[idx]
        return None

    def hasNext(self) -> bool:
        return any(idx < len(v) for v, idx in self.data)

⏱️ Time and Space Complexity

MetricValueTime per next()O(1)Time per hasNext()O(1)Space ComplexityO(k) where k is number of input lists

🌟 Extension Idea

• Extend to k vectors → use a queue of (iterator, index) pairs
• Can generalize to round-robin iteration of many input sources

✅ Conclusion

LeetCode 281: Zigzag Iterator is a great exercise in designing clean, modular iteration logic. Whether it's two lists or k, the principle is the same: alternate access and only keep going if data exists.

It’s a perfect prep problem for systems where multiple data streams need interleaving, like paginated APIs or round-robin schedulers.