C++ O(1) space and follow up for k vectors


  • 0
    class ZigzagIterator {
    public:
        ZigzagIterator(vector<int>& v1, vector<int>& v2) {
            it1 = v1.begin();
            it2 = v2.begin();
            end1 = v1.end();
            end2 = v2.end();
        }
    
        int next() {
            if(it1 == end1) return *it2++;
            if(it2 == end2) return *it1++;
            int res = turn ? *it1++ : *it2++;
            turn = !turn;
            return res;
        }
    
        bool hasNext() {
            return it1 != end1 || it2 != end2;
        }
    
    private:
        vector<int>::iterator it1, it2, end1, end2;
        bool turn = true;
    };
    

    For k vectors, use two queues to store iterators and end iterators.

    class ZigzagIterator {
    public:
        ZigzagIterator(vector<int>& v1, vector<int>& v2) {
            auto it1 = v1.begin();
            auto it2 = v2.begin();
            auto end1 = v1.end();
            auto end2 = v2.end();
            it.push_back(it1);
            it.push_back(it2);
            end.push_back(end1);
            end.push_back(end2);
            /*  If given k vectors
            (vector<vector<int>>& v){
                for(auto x: v){
                    auto i = v.begin(); 
                    auto j = v.end();
                    it.push_back(i);
                    end.push_back(j);
                }
            }
            */
        }
    
        int next() {
            auto x = it.front();
            it.pop_front();
            int res = *x++;
            it.push_back(x);
            end.push_back(end.front());
            end.pop_front();
            return res;
        }
    
        bool hasNext() {
            while(!it.empty() && it.front() == end.front()){
                it.pop_front();
                end.pop_front();
            }
            return !it.empty();
        }
    
    private:
        deque<vector<int>::iterator>it;
        deque<vector<int>::iterator>end;
    };
    

Log in to reply
 

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