Zigzag Iterator

Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

  1. v1 = [1, 2]
  2. v2 = [3, 4, 5, 6]

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

Follow up: 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”. For example, given the following input:

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

It should return [1,4,8,2,5,9,3,6,7].

Solution:

  1. public class ZigzagIterator {
  2.   int i1 = 0;
  3.   int i2 = 0;
  5.   boolean flag = false;
  7.   List<Integer> l1;
  8.   List<Integer> l2;
  10.   public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
  11.     l1 = v1;
  12.     l2 = v2;
  13.   }
  15.   public int next() {
  16.     flag = !flag;
  18.     if (i1 < l1.size() && (flag  || i2 >= l2.size())) 
  19.       return l1.get(i1++);
  21.     if (i2 < l2.size() && (!flag || i1 >= l1.size())) 
  22.       return l2.get(i2++);
  24.     return -1;
  25.   }
  27.   public boolean hasNext() {
  28.     return i1 < l1.size() || i2 < l2.size();
  29.   }
  30. }
  32. /**
  33.  * Your ZigzagIterator object will be instantiated and called as such:
  34.  * ZigzagIterator i = new ZigzagIterator(v1, v2);
  35.  * while (i.hasNext()) v[f()] = i.next();
  36.  */