Zigzag Iterator

medium design iterator queue

Problem

Given multiple integer lists, design an iterator that returns their elements alternately: v1[0], v2[0], …, vk[0], v1[1], v2[1], …, vk[1], etc., skipping any exhausted list.

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

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

Round-robin across lists; once v1 is exhausted, v2 streams alone.

lists (rows by ';', cells by ',')

from collections import deque
class ZigzagIterator:
    def __init__(self, *vs):
        self.q = deque()
        for v in vs:
            if v: self.q.append((v, 0))
    def next(self):
        v, i = self.q.popleft()
        if i + 1 < len(v):
            self.q.append((v, i + 1))
        return v[i]
    def hasNext(self):
        return bool(self.q)

class ZigzagIterator {
  constructor(...vs) {
    this.q = [];
    for (const v of vs) if (v.length) this.q.push([v, 0]);
  }
  next() {
    const [v, i] = this.q.shift();
    if (i + 1 < v.length) this.q.push([v, i + 1]);
    return v[i];
  }
  hasNext() { return this.q.length > 0; }
}

class ZigzagIterator {
    Deque q = new ArrayDeque<>();
    List> data = new ArrayList<>();
    public ZigzagIterator(List... vs) {
        for (List v : vs) {
            if (!v.isEmpty()) { data.add(v); q.add(new int[]{ data.size() - 1, 0 }); }
        }
    }
    public int next() {
        int[] p = q.poll();
        int v = data.get(p[0]).get(p[1]);
        if (p[1] + 1 < data.get(p[0]).size()) q.add(new int[]{ p[0], p[1] + 1 });
        return v;
    }
    public boolean hasNext() { return !q.isEmpty(); }
}

class ZigzagIterator {
    deque*, int>> q;
public:
    ZigzagIterator(initializer_list*> vs) {
        for (auto* v : vs) if (!v->empty()) q.push_back({ v, 0 });
    }
    int next() {
        auto [v, i] = q.front(); q.pop_front();
        if (i + 1 < (int)v->size()) q.push_back({ v, i + 1 });
        return (*v)[i];
    }
    bool hasNext() { return !q.empty(); }
};

Explanation

We want to pull one element from each list in turn — list 1, list 2, ..., then back to list 1 — and skip any list that has run out. A queue makes this round-robin behavior fall out almost for free.

We start by putting a little cursor for each non-empty list into the queue. Each cursor is a pair (list, index) pointing at the next value to emit from that list.

Every call to next() pops the cursor at the front of the queue, reads its current value, and — if that list still has more items — pushes an advanced cursor (list, index + 1) to the back. Pushing to the back is what gives the fair, alternating order.

When a list is exhausted we simply do not re-enqueue it, so it naturally drops out and the remaining lists keep cycling. hasNext() is just "is the queue non-empty?".

Example: v1 = [1,2], v2 = [3,4,5,6]. Queue starts as [(v1,0),(v2,0)]. We emit 1, push (v1,1); emit 3, push (v2,1); emit 2 (v1 done); then 4,5,6 stream from v2 alone → [1,3,2,4,5,6].

Time: O(1) per next Space: O(k)