# [leetcode] Zigzag Iterator

Zigzag Iterator

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

For example, given two 1d vectors:

```v1 = [1, 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?

Clarification for the follow up question – Update (2015-09-18):
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,2,3]
[4,5,6,7]
[8,9]
```

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

Keep the invariant in mind.

```//invariant keep row, col always points to next available element
class ZigzagIterator {
public:
vector<vector<int>> data;
int row, col;
bool isEnd;
ZigzagIterator(vector<int>& v1, vector<int>& v2) {
data.push_back(v1);
data.push_back(v2);
row = col = 0;
isEnd = false;
while(row < data.size() && data[row].size() == 0){
row++;
}
if(row == data.size()){
isEnd = true;
}
}

int next() {
int ans = data[row][col];
row++;
while(row < data.size() && data[row].size() <= col){
row++;
}
if(row == data.size()){
row = 0;
col++;
}
while(row < data.size() && data[row].size() <= col){
row++;
}
if(row == data.size()){
isEnd = true;
}
return ans;
}

bool hasNext() {
return !isEnd;
}
};

/**
* Your ZigzagIterator object will be instantiated and called as such:
* ZigzagIterator i(v1, v2);
* while (i.hasNext()) cout << i.next();
*/```

This site uses Akismet to reduce spam. Learn how your comment data is processed.