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
- 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.
next()advances the rotation index and returns the next element from whichever vector is not exhausted, skipping any that are.- The
while Trueloop is safe becausenext()is only called whenhasNext()is true, so at least one vector still has elements. hasNext()is ananyover the read positions. The design generalises tokvectors 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 guaranteeshasNext()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.