# C++ concise solution O(1) time and O(k) space using list of iterator pairs (for k given vectors)

• The key idea is to use a pair of `vector<int>::iterator>`to record the current and end positions of a vector and use a `list` to store such pairs for arbitrary `_n`given vectors. The design to use a `list`to collect information of all vectors is to be able to perform `O(1)`removal once all elements of a vector is exhausted (which can significantly speed up entry look-up in `next()`). Both `next()`and `hasNext()`are `O(1)`time and constructor is `O(_n)`time to initialize class members as well as removing empty vectors if there is any.

``````class ZigzagIterator {
typedef pair<vector<int>::iterator, vector<int>::iterator> PIt;
private:
list<PIt> _its; // list of pair(current position, end), max size is _n
int _n; list<PIt>::iterator _cur; // current vector
public:
ZigzagIterator(vector<int>& v1, vector<int>& v2):_n(2) { // O(_n)
_its.emplace_back(v1.begin(), v1.end());
_its.emplace_back(v2.begin(), v2.end());
for (_cur = _its.begin(); _cur != _its.end();) // remove empty vector(s)
if (_cur->first == _cur->second) _cur = _its.erase(_cur); else ++_cur;
_cur = _its.begin();
}

int next() { // O(1)
if (!hasNext()) return INT_MIN;
int res = *_cur->first++;
if (_cur->first == _cur->second) _cur = _its.erase(_cur); else ++_cur;
if (_cur == _its.end()) _cur = _its.begin();
return res;
}

bool hasNext() { return !_its.empty(); } // O(1)
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.