LeetCode 281: Zigzag Iterator Solution in Python – A Step-by-Step Guide

What Is LeetCode 281: Zigzag Iterator?

In LeetCode 281: Zigzag Iterator, you’re given two 1D integer lists (e.g., v1 and v2), and your job is to create an iterator class with two methods: next() to return the next element in the zigzag order, and hasNext() to check if there’s more to come. The zigzag pattern means taking one element from v1, then one from v2, then back to v1, and so on, until both lists are exhausted. For example, with v1 = [1, 2] and v2 = [3, 4, 5], the output sequence is [1, 3, 2, 4, 5]. This problem tests your ability to manage multiple data sources, sharing a vibe with iterator challenges like LeetCode 251: Flatten 2D Vector.

Problem Statement

• Input: Two integer lists v1 and v2.
• Output: An iterator class with:
• next(): Returns the next integer in zigzag order.
• hasNext(): Returns True if more elements remain, False otherwise.
• Rules: Alternate between v1 and v2; if one list runs out, continue with the other.

Constraints

• List lengths: 0 to 10³ (1,000).
• Element values: -10⁹ to 10⁹.

Examples

• Input: v1 = [1, 2], v2 = [3, 4, 5]
• Calls: next() → 1, next() → 3, next() → 2, next() → 4, next() → 5
• Output: [1, 3, 2, 4, 5]
• Input: v1 = [], v2 = [1]
• Calls: next() → 1
• Output: [1]
• Input: v1 = [1, 2, 3], v2 = [4]
• Calls: next() → 1, next() → 4, next() → 2, next() → 3
• Output: [1, 4, 2, 3]

Understanding the Problem: Weaving the Lists

To solve LeetCode 281: Zigzag Iterator in Python, we need to design an iterator that interleaves two lists, pulling one element at a time in alternating fashion, and keeps going with any leftovers when one list runs out. A naive approach might merge the lists upfront, but that’s not iterator-style—we need to fetch elements on demand. We’ll use: 1. Best Solution (Queue-Based): O(1) time per call, O(k) space (k = number of lists, here 2)—flexible and elegant. 2. Alternative Solution (Pointer-Based): O(1) time per call, O(1) space—simple and minimal.

Let’s dive into the queue-based solution with a beginner-friendly breakdown.

Best Solution: Queue-Based Approach

Why This Is the Best Solution

The queue-based approach is tops for LeetCode 281 because it’s both efficient—O(1) time for next() and hasNext()—and extensible. It uses a queue to track which list is up next, popping and pushing as needed, making it easy to scale to more than two lists (a bonus for real-world scenarios). For beginners, it’s like a to-do list that keeps the zigzag order straight without fuss.

How It Works

Think of this as managing two workers passing you items: one from v1, one from v2. You put them in a line (queue), take the first worker’s item, then send them back with their next task—repeating until they’re both out of stuff. Here’s the step-by-step, explained simply:

• Step 1: Set Up the Queue:
• Create a queue of tuples: (list, index), where list is v1 or v2, and index tracks the next element.
• Add (v1, 0) and (v2, 0) if they’re not empty.

• Step 2: next() Method:
• Pop the front tuple (current list, current index).
• Return the element at that index.
• If more elements remain in that list, increment the index and push it back to the queue.

• Step 3: hasNext() Method:
• Check if the queue is empty—True if not, False if it is.

• Step 4: Why It Works:
• Queue ensures alternating order: v1, v2, v1, v2...
• When one list empties, the other keeps going naturally.
• It’s like a round-robin schedule—everyone gets a turn!

Step-by-Step Example

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

• Init: Queue = [(v1, 0), (v2, 0)].
• next(): Pop (v1, 0) → return 1, push (v1, 1). Queue = [(v2, 0), (v1, 1)].
• next(): Pop (v2, 0) → return 3, push (v2, 1). Queue = [(v1, 1), (v2, 1)].
• next(): Pop (v1, 1) → return 2, v1 done. Queue = [(v2, 1)].
• next(): Pop (v2, 1) → return 4, push (v2, 2). Queue = [(v2, 2)].
• next(): Pop (v2, 2) → return 5, v2 done. Queue = [].
• hasNext(): False.
• Result: [1, 3, 2, 4, 5].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down for beginners:

Copy codefrom collections import deque

class ZigzagIterator:
    def __init__(self, v1: List[int], v2: List[int]):
        # Step 1: Initialize queue with (list, index) pairs
        self.queue = deque()
        if v1:
            self.queue.append((v1, 0))
        if v2:
            self.queue.append((v2, 0))

    def next(self) -> int:
        # Step 2: Get next element
        if not self.queue:
            return None  # Shouldn’t happen with hasNext check
        curr_list, idx = self.queue.popleft()
        val = curr_list[idx]
        # If more elements, add back with next index
        if idx + 1 < len(curr_list):
            self.queue.append((curr_list, idx + 1))
        return val

    def hasNext(self) -> bool:
        # Step 3: Check if more elements remain
        return len(self.queue) > 0

• Line 5-9: Queue starts with (v1, 0) and (v2, 0) if lists aren’t empty—our zigzag lineup.
• Line 12-19: next():
• Pop the front tuple: which list and where we’re at.
• Grab the value at that index.
• If the list has more, push it back with the next index.
• Return the value.
• Line 22-23: hasNext(): True if queue’s not empty—more to process!

• Time Complexity: O(1) per call—queue ops are constant.
• Space Complexity: O(1) or O(k) where k=2 here—just the queue.

This solution is like a conveyor belt—smooth and steady!

Alternative Solution: Pointer-Based Approach

Why an Alternative Approach?

The pointer-based method uses two indices to track progress in v1 and v2, switching between them manually. It’s O(1) time per call and O(1) space—super lightweight—but less flexible for scaling to more lists. It’s like juggling two balls, keeping track of whose turn it is.

How It Works

Picture yourself pointing at the next item in each list, picking one, moving that pointer, and switching hands:

• Step 1: Track indices for v1 and v2, and whose turn it is.
• Step 2: next() picks from the current list, advances its pointer, and flips the turn.
• Step 3: hasNext() checks if either list has elements left.

It’s a straightforward back-and-forth dance!

Step-by-Step Example

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

• Init: i1=0, i2=0, turn=0 (v1 first).
• next(): turn=0, v1[0]=1, i1=1, turn=1.
• next(): turn=1, v2[0]=3, i2=1, turn=0.
• next(): turn=0, v1[1]=2, i1=2, turn=1.
• next(): turn=1, v2[1]=4, i2=2, turn=0.
• next(): turn=1 (v1 done), v2[2]=5, i2=3.
• Result: [1, 3, 2, 4, 5].

Code for Pointer-Based Approach

Copy codeclass ZigzagIterator:
    def __init__(self, v1: List[int], v2: List[int]):
        self.v1 = v1
        self.v2 = v2
        self.i1 = 0  # Pointer for v1
        self.i2 = 0  # Pointer for v2
        self.turn = 0  # 0 for v1, 1 for v2

    def next(self) -> int:
        if self.turn == 0 and self.i1 < len(self.v1):
            val = self.v1[self.i1]
            self.i1 += 1
        elif self.i2 < len(self.v2):
            val = self.v2[self.i2]
            self.i2 += 1
        else:
            val = self.v1[self.i1]
            self.i1 += 1
        self.turn = 1 - self.turn  # Flip turn
        return val

    def hasNext(self) -> bool:
        return self.i1 < len(self.v1) or self.i2 < len(self.v2)

• Time Complexity: O(1) per call.
• Space Complexity: O(1)—just pointers.

It’s lean and mean!

Comparing the Two Solutions

• Queue-Based (Best):
• Pros: O(1) time, extensible to k lists, clean logic.
• Cons: Slight space overhead (O(k)).
• Pointer-Based (Alternative):
• Pros: O(1) time and space, minimal footprint.
• Cons: Less scalable, more manual control.

Queue wins for flexibility.

Additional Examples and Edge Cases

• Empty Lists: v1 = [], v2 = [1] → [1].
• One Empty: v1 = [1, 2], v2 = [] → [1, 2].
• Single Element: v1 = [1], v2 = [2] → [1, 2].

Both handle these perfectly.

Complexity Breakdown

• Queue: Time O(1) per call, Space O(1) or O(k=2).
• Pointer: Time O(1), Space O(1).

Queue’s slight edge is scalability.

Key Takeaways

• Queue: Line up tasks for smooth zigzagging.
• Pointer: Juggle indices for simplicity.
• Iterators: Fetch on demand—cool stuff!
• Python Tip: Queues and loops shine—see [Python Basics](/python/basics).

Final Thoughts: Zigzag Like a Pro

LeetCode 281: Zigzag Iterator in Python is a neat twist on iteration. The queue-based solution keeps it flexible and fun, while pointers offer a minimalist vibe. Want more? Check LeetCode 251: Flatten 2D Vector or LeetCode 341: Flatten Nested List Iterator. Ready to weave? Head to Solve LeetCode 281 on LeetCode and zigzag your way through today!