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

  • 0

    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 _ngiven vectors. The design to use a listto 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;
        list<PIt> _its; // list of pair(current position, end), max size is _n
        int _n; list<PIt>::iterator _cur; // current vector
        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)

Log in to reply

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