Zigzag Iterator solution and explanation
Google
8 more videos on this problem
281. Zigzag IteratorMuerde un zombie · 4:43 · 1K views
Zigzag Iterator (Medium), C++, LeetcodeH William Polenz · 12:42 · 975 views
Leetcode 281. Zigzag IteratorLetsCode · 3:23 · 789 views
Zig Zag IteratorOwen Wu · 3:18 · 506 views
281. Zigzag Iterator | LeetCode Premium GoogleShivam Gupta · 6:45 · 262 views
Zigzag Iterator (2 Solutions!!)Roel Van de Paar · 3:28 · 236 views
Daily Leetcode #2213: Apr 22, 2026 - 281. Zigzag IteratorProgramming Live with Larry · 11:28 · 226 views
#LeetCode 281 | Zigzag Iterator #JavaSleepy Cracker · 5:42 · 123 views
Leetcode 281. Zigzag Iterator in Python | Python Leetcode | Python Coding Tutorial | Python ASMRCode is Art · 1:54 · 36 views
The problem
Given two vectors of integers v1 and v2, implement an iterator to return their elements alternately.
Implement the ZigzagIterator class:
ZigzagIterator(List<int> v1, List<int> v2)initializes the object with the two vectorsv1andv2.boolean hasNext()returnstrueif the iterator still has elements, andfalseotherwise.int next()returns the current element of the iterator and moves the iterator to the next element.
Example 1:
Input: v1 = [1,2], v2 = [3,4,5,6] Output: [1,3,2,4,5,6] Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].
Example 2:
Input: v1 = [1], v2 = [] Output: [1]
Example 3:
Input: v1 = [], v2 = [1] Output: [1]
Constraints:
0 <= v1.length, v2.length <= 10001 <= v1.length + v2.length <= 2000-231 <= v1[i], v2[i] <= 231 - 1
Follow up: What if you are given k vectors? How well can your code be extended to such cases?
Clarification for the follow-up question:
The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic".
Follow-up Example:
Input: v1 = [1,2,3], v2 = [4,5,6,7], v3 = [8,9] Output: [1,4,8,2,5,9,3,6,7]
Approach overview
Problem Overview: You receive two integer arrays and must iterate through them in alternating order. The iterator should return elements like v1[0], v2[0], v1[1], v2[1] and continue until both arrays are exhausted.
Approach 1: Pointer + Turn Simulation (O(n) time, O(1) space)
Maintain two indices i and j for the arrays and a boolean flag indicating whose turn it is. On each call to next(), return the element from the current array if it still has elements; otherwise switch to the other array. The iterator advances the corresponding pointer after returning a value. This works because the arrays are accessed sequentially, but the logic becomes messy when one array finishes earlier and the turn flag must be skipped repeatedly.
Approach 2: Queue of Iterators (O(n) time, O(k) space)
Store active iterators in a queue. Initially push iterators for both arrays if they are non‑empty. When next() is called, pop the front iterator, return its next element, and push it back if it still has remaining elements. This naturally rotates between arrays and automatically handles uneven lengths. The queue size is at most k (number of arrays), which is 2 in this problem but generalizes easily.
The key insight: alternating order is essentially round‑robin scheduling. A queue perfectly models this behavior. Each iterator gets one turn, then moves to the back until it runs out of elements.
This design approach is common in iterator problems and appears in tasks involving cyclic traversal or multi-source iteration. Understanding how to manage state with a queue and implement a custom iterator interface is the main learning goal. The input itself is just an array, but the challenge is designing a clean iteration mechanism.
Recommended for interviews: The queue-of-iterators solution is the expected answer. It keeps the code clean, avoids complicated condition checks, and generalizes to more than two arrays. Mentioning the pointer simulation approach first shows you understand the basic mechanics, but implementing the queue-based iterator demonstrates stronger design skills.
Solution
class ZigzagIterator:
def __init__(self, v1: List[int], v2: List[int]):
self.cur = 0
self.size = 2
self.indexes = [0] * self.size
self.vectors = [v1, v2]
def next(self) -> int:
vector = self.vectors[self.cur]
index = self.indexes[self.cur]
res = vector[index]
self.indexes[self.cur] = index + 1
self.cur = (self.cur + 1) % self.size
return res
def hasNext(self) -> bool:
start = self.cur
while self.indexes[self.cur] == len(self.vectors[self.cur]):
self.cur = (self.cur + 1) % self.size
if self.cur == start:
return False
return True
# Your ZigzagIterator object will be instantiated and called as such:
# i, v = ZigzagIterator(v1, v2), []
# while i.hasNext(): v.append(i.next())public class ZigzagIterator {
private int cur;
private int size;
private List<Integer> indexes = new ArrayList<>();
private List<List<Integer>> vectors = new ArrayList<>();
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
cur = 0;
size = 2;
indexes.add(0);
indexes.add(0);
vectors.add(v1);
vectors.add(v2);
}
public int next() {
List<Integer> vector = vectors.get(cur);
int index = indexes.get(cur);
int res = vector.get(index);
indexes.set(cur, index + 1);
cur = (cur + 1) % size;
return res;
}
public boolean hasNext() {
int start = cur;
while (indexes.get(cur) == vectors.get(cur).size()) {
cur = (cur + 1) % size;
if (start == cur) {
return false;
}
}
return true;
}
}
/**
* Your ZigzagIterator object will be instantiated and called as such:
* ZigzagIterator i = new ZigzagIterator(v1, v2);
* while (i.hasNext()) v[f()] = i.next();
*/type ZigzagIterator struct {
cur int
size int
indexes []int
vectors [][]int
}
func Constructor(v1, v2 []int) *ZigzagIterator {
return &ZigzagIterator{
cur: 0,
size: 2,
indexes: []int{0, 0},
vectors: [][]int{v1, v2},
}
}
func (this *ZigzagIterator) next() int {
vector := this.vectors[this.cur]
index := this.indexes[this.cur]
res := vector[index]
this.indexes[this.cur]++
this.cur = (this.cur + 1) % this.size
return res
}
func (this *ZigzagIterator) hasNext() bool {
start := this.cur
for this.indexes[this.cur] == len(this.vectors[this.cur]) {
this.cur = (this.cur + 1) % this.size
if start == this.cur {
return false
}
}
return true
}
/**
* Your ZigzagIterator object will be instantiated and called as such:
* obj := Constructor(param_1, param_2);
* for obj.hasNext() {
* ans = append(ans, obj.next())
* }
*/struct ZigzagIterator {
v1: Vec<i32>,
v2: Vec<i32>,
/// `false` represents `v1`, `true` represents `v2`
flag: bool,
}
impl ZigzagIterator {
fn new(v1: Vec<i32>, v2: Vec<i32>) -> Self {
Self {
v1,
v2,
// Initially beginning with `v1`
flag: false,
}
}
fn next(&mut self) -> i32 {
if !self.flag {
// v1
if self.v1.is_empty() && !self.v2.is_empty() {
self.flag = true;
let ret = self.v2.remove(0);
return ret;
}
if self.v2.is_empty() {
let ret = self.v1.remove(0);
return ret;
}
let ret = self.v1.remove(0);
self.flag = true;
return ret;
} else {
// v2
if self.v2.is_empty() && !self.v1.is_empty() {
self.flag = false;
let ret = self.v1.remove(0);
return ret;
}
if self.v1.is_empty() {
let ret = self.v2.remove(0);
return ret;
}
let ret = self.v2.remove(0);
self.flag = false;
return ret;
}
}
fn has_next(&self) -> bool {
!self.v1.is_empty() || !self.v2.is_empty()
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pointer + Turn Simulation | O(n) | O(1) | Simple cases with only two arrays and minimal abstraction needed |
| Queue of Iterators (Round Robin) | O(n) | O(k) | Preferred design approach; clean logic and easily extends to multiple arrays |
Frequently asked questions
Is Zigzag Iterator easy or hard?
Zigzag Iterator is rated Medium difficulty. The iteration itself is simple, but designing a clean iterator interface and handling uneven array lengths correctly requires careful state management.
Zigzag Iterator Python/Java solution
Python and Java implementations typically store iterators or index pairs inside a queue. The next() method pops the front iterator, returns the next value, and re-enqueues it if elements remain. This keeps the iteration logic concise and efficient.
How to solve Zigzag Iterator in O(n)?
Use a queue that stores iterators or index references for each array. Pop the front iterator, output its next element, and push it back if more elements remain. Since each element is visited exactly once and queue operations are constant time, the solution runs in O(n).
What is the best approach for Zigzag Iterator?
The queue-of-iterators approach is the most robust solution. Maintain a queue containing iterators for each array. Each call to next() pops the front iterator, returns its value, and pushes it back if more elements remain. This achieves O(n) total time and O(k) space where k is the number of arrays.
Is Zigzag Iterator asked at Google/Amazon/Meta?
Zigzag Iterator has appeared in interviews at companies like Google and Meta, especially in roles focused on data structures and system design fundamentals. It evaluates understanding of iterators, queues, and clean state management.
What data structure is used in Zigzag Iterator?
A queue is the primary data structure used in the optimal solution. It maintains the order of active iterators and enables round-robin traversal. Arrays store the input values, while the queue controls the iteration sequence.
What is the time complexity of Zigzag Iterator?
The overall time complexity is O(n), where n is the total number of elements across both arrays. Each element is processed exactly once, and queue operations like push and pop are O(1). Space complexity is O(k) for storing active iterators.