[LintCode] Problem 541 - Zigzag Iterator II

Posted on | In ,

Follow up Zigzag Iterator: What if you are given k 1d vectors? How well can your code be extended to such cases? 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”.

Example

No.1

Input: k = 3

1
2
3
4
5
vecs = [
    [1,2,3],
    [4,5,6,7],
    [8,9],
]

Output: [1,4,8,2,5,9,3,6,7]

No.2

Input: k = 3

1
2
3
4
5
vecs = [
    [1,1,1]
    [2,2,2]
    [3,3,3]
]

Output: [1,2,3,1,2,3,1,2,3]

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
private Queue<Iterator> queue = new LinkedList<>();

public ZigzagIterator2(List<List<Integer>> vecs) {
    for (List<Integer> vec : vecs) {
        if (!vec.isEmpty())
            queue.offer(vec.iterator());
    }
}

public int next() {
    Iterator iterator = queue.poll();
    int next = (int) iterator.next();

    if (iterator.hasNext())
        queue.offer(iterator);

    return next;
}

public boolean hasNext() {
    return !queue.isEmpty();
}