Very concise C++ solution using vector::iterator (extensible to k vectors)

  • 0

    Since we are implementing iterators, using vector::iteratoris my natural choice. The constant variable _n = 2 can easily be replaced by a generic number of vectors to extend to kvector case.
    The time complexity for next()is O(_n). Actually, one can improve the time efficiency by replacing vector<vector<int>::iterator> with list<vector<int>::iterator> and _cur with a list iterator and erasing any empty iterator whenever it reached end, so we do not have to traverse through empty iterators if not many values left in the vectors.

    class ZigzagIterator {
        vector<vector<int>::iterator> _its, _itends;
        int _n, _cur; // number of arrays, index of current array
        ZigzagIterator(vector<int>& v1, vector<int>& v2):_n(2),_cur(0) {
          _its.push_back(v1.begin()); _its.push_back(v2.begin());
          _itends.push_back(v1.end()); _itends.push_back(v2.end());
          // find first non-empty array
          while (_cur < _n && _its[_cur] == _itends[_cur]) ++_cur;
        int next() {
          if (!hasNext()) return INT_MIN;
          int res = *_its[_cur]++; // get result and go to next value
          int copy_cur = (++_cur %=_n); // go to next array
          // find next non-empty array
          while (_cur < _n && _its[_cur] == _itends[_cur])
            if ((++_cur%=_n) == copy_cur) _cur = _n; // set _cur invalid
          return res;
        bool hasNext() { return _cur < _n; }

Log in to reply

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