⚡Flashcard Drill➔
NeetCode #33LC-281MediumArrays & HashingNC Algo100
← Back to All Problems

#33 · #281 · Zigzag Iterator(锯齿迭代器)

📌 Problem Statement & Constraints

Given two vectors v1 and v2, implement an iterator that returns their elements in alternating order, starting with v1. If one vector is exhausted, continue with the other. Implement next() and hasNext(). Constraints: 0 <= v1.length, v2.length <= 1000.

💡 Core Algorithmic Approaches

  1. Keep the two vectors in an array along with a per-vector read position, plus an index of which vector is next in the rotation.
  2. next() advances the rotation index and returns the next element from whichever vector is not exhausted, skipping any that are.
  3. The while True loop is safe because next() is only called when hasNext() is true, so at least one vector still has elements.
  4. hasNext() is an any over the read positions. The design generalises to k vectors simply by growing the array.

💻 Benchmark Python3 Implementation

class ZigzagIterator:
    def __init__(self, v1: List[int], v2: List[int]):
        self.vs = [v1, v2]                 # easily extended to k vectors
        self.pos = [0, 0]
        self.turn = 0

    def next(self) -> int:
        while True:
            i = self.turn
            self.turn = (self.turn + 1) % len(self.vs)   # round-robin
            if self.pos[i] < len(self.vs[i]):
                v = self.vs[i][self.pos[i]]
                self.pos[i] += 1
                return v

    def hasNext(self) -> bool:
        return any(self.pos[i] < len(self.vs[i]) for i in range(len(self.vs)))

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) amortised per next() call: the loop skips at most one exhausted vector per step, and hasNext is O(k) with k = 2.
💾 Space Complexity
O(k) for the position array; the input vectors are not copied.

⚠️ Interview Pitfalls & Follow-ups

  • Assuming both vectors have equal length: they need not, so the alternating logic must handle exhaustion.
  • Advancing the turn index only when an element is returned: it must advance every iteration of the skip loop, otherwise an exhausted vector blocks progress.
  • Using a single global index into a flattened array: this destroys the alternating order, which is the entire point.
  • Raising when next() is called on an exhausted iterator: the contract guarantees hasNext() is checked first, but a defensive guard is fine.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems