# Question

Formatted question description: https://leetcode.ca/all/281.html

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 vectors v1 and v2.
• boolean hasNext() returns true if the iterator still has elements, and false otherwise.
• 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 <= 1000
• 1 <= 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]


# Algorithm

### Extra space to save

For class initialization, the two arrays are stored in another one-bit array in the order of zigzag, then the values in the new array are printed in order.

• need extra space

### No extra space

Use two variables i and j to record the current element positions of the two vectors, and initialize them to 0.

Then when i<=j, it means that you need to print the elements of v1 array, otherwise, print the elements of v2 array.

In the hasNext() function, when i or j is printed equal to the length of the corresponding array, assign it to an extra large value, which does not affect the printing of the value of the other array, only when i and j both exceed the length of the lattice array, return false.

Queue to hold a pair of iterators/indexes. During initialization, add iterator/index pairs and put them in the queue for every iterator. At initialization, each pair stores the the first and last index of the iterator.

In the next() function, take out a pair at the head of the queue. If the current iterator is not equal to end(), store the pari (iterator and the next index) to the queue, and then return the value at the current index.

In the hasNext() function, you only need to see if the queue is empty.

# Code

• public class Zigzag_Iterator {

public static void main(String[] args) {

List<Integer> v1 = Arrays.asList(1,2);
List<Integer> v2 = Arrays.asList(3, 4, 5, 6);

Zigzag_Iterator out = new Zigzag_Iterator();
ZigzagIterator z = out.new ZigzagIterator(v1, v2);

while (z.hasNext()) {
System.out.println(z.next());
}

List<Integer> v3 = Arrays.asList(1,2,3);
List<Integer> v4 = Arrays.asList(4,5,6,7);
List<Integer> v5 = Arrays.asList(8,9);

List<List<Integer>> vectors = Arrays.asList(v3, v4, v5);
ZigzagIteratorK zk = out.new ZigzagIteratorK(vectors);

while (zk.hasNext()) { // [1,4,8,2,5,9,3,6,7]
System.out.println(zk.next());
}
}

public class ZigzagIteratorK {

// int[0] is index of vector of vectors list, int[1] is start of a vector, int[2] is end

//        Map<Integer, List<Integer>> vectorsIndexMap = new HashMap<>(); // no map needed, if move 'vectors' a class variable
List<List<Integer>> vectors;

public ZigzagIteratorK(List<List<Integer>> vectors) {
this.vectors = vectors;
for (int i = 0; i < vectors.size(); i++) {
q.offer(new int[]{i, 0, vectors.get(i).size()});
//                vectorsIndexMap.put(i, vectors.get(i));
}
}

public int next() {
int[] current = q.poll();

int i = current[0];
int start = current[1];
int end = current[2];

if (start + 1 < end) {
q.offer(new int[]{i, start + 1, end});
}

//            return vectorsIndexMap.get(i).get(start);
return vectors.get(i).get(start);
}

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

// ZigzagIterator K个也适用
public class ZigzagIterator_builtinIterator {
List<Iterator<Integer>> iters = new ArrayList<Iterator<Integer> >();

int count = 0;

public ZigzagIterator_builtinIterator(List<Integer> v1, List<Integer> v2) {
if( !v1.isEmpty() ) {
}
if( !v2.isEmpty() ) {
}
}

public int next() {
int x = iters.get(count).next();
if(!iters.get(count).hasNext()) { // remove iterator from list
iters.remove(count);
} else {
count++;
}

if(iters.size() != 0) {
count %= iters.size(); // mod to decide which iterator to get value
}
return x;
}

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

public class ZigzagIterator {

List<Integer> result = new ArrayList<>(); // this is extra o(N) space solution, can just maintain a boolean variable
int index = 0;

public ZigzagIterator(List<Integer> v1, List<Integer> v2) {

for (int i = 0; i < Math.max(v1.size(), v2.size()); i++) {
if (i < v1.size()) {
}
if (i < v2.size()) {
}
}
}

public int next() {
return result.get(index++);
}

public boolean hasNext() {
return index < result.size();
}
}
}

############

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;
}

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();
*/

• // OJ: https://leetcode.com/problems/zigzag-iterator/
// Time:
//   ZigzagIterator: O(K)
//   next: O(1)
//   hasNext: O(1)
// Space: O(K) where K is the number of input vectors
class ZigzagIterator {
private:
queue<pair<vector<int>::iterator, vector<int>::iterator>> q;
public:
ZigzagIterator(vector<int>& v1, vector<int>& v2) {
if (v1.begin() != v1.end()) q.push(make_pair(v1.begin(), v1.end()));
if (v2.begin() != v2.end()) q.push(make_pair(v2.begin(), v2.end()));
}
int next() {
auto p = q.front();
q.pop();
int val = *p.first;
p.first++;
if (p.first != p.second) q.push(p);
return val;
}
bool hasNext() {
return q.size();
}
};

• class ZigzagIteratorK:

# int[0] is index of vector of vectors list, int[1] is start of a vector, int[2] is end
q = []

# no map needed, if move 'vectors' a class variable
vectors = []

def __init__(self, vectors):
self.vectors = vectors
for i in range(len(vectors)):
self.q.append([i, 0, len(vectors[i])])

def next(self):
current = self.q.pop(0)

i = current[0]
start = current[1]
end = current[2]

if start + 1 < end:
self.q.append([i, start + 1, end])

return self.vectors[i][start]

def hasNext(self):
return len(self.q) != 0

############

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())

############

'''
iter() - builtin function, return an iterator object
https://docs.python.org/3/library/functions.html#iter

>>> a = map(iter, [[1,2],[3,4]])
>>>
>>> b = next(a)
>>> b
<list_iterator object at 0x101630280>
>>> next(b)
1
>>> next(b)
2
>>> next(b)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration

>>> b = deque(map(iter, [[1,2],[3,4]]))
>>>
>>> c = b.popleft()
>>> c
<list_iterator object at 0x1016304f0>
>>> c.next()
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
AttributeError: 'list_iterator' object has no attribute 'next'
>>> next(c)
1
>>> next(c)
2
>>> next(c)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
StopIteration

len(s) - Return the length (the number of items) of an object
https://docs.python.org/3/library/functions.html#len
'''

from collections import deque

class ZigzagIterator(object):

def __init__(self, v1, v2):
"""
:type v1: List[int]
:type v2: List[int]
"""
self.iters = deque(map(iter, [v1, v2]))
self.total = sum(map(len, [v1, v2]))

def next(self):
"""
:rtype: int
"""
top = self.iters.popleft()
try:
value = top.next()
except StopIteration:
return self.next()
self.total -= 1
if self.total != 0:
self.iters.append(top)
return value

def hasNext(self):
"""
:rtype: bool
"""
return self.total > 0

# Your ZigzagIterator object will be instantiated and called as such:
# i, v = ZigzagIterator(v1, v2), []
# while i.hasNext(): v.append(i.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()
}
}