281. Zigzag Iterator

Given two vectors of integers v1 and v2, implement an iterator to return their elements alternately.

Implement the ZigzagIterator class:

• ZigzagIterator(List v1, List v2) initializes the object with the two vectors v1 and v2.
• boolean hasNext() returns true if the iterator still has elements, and false otherwise.
• int next() returns the current element of the iterator and moves the iterator to the next element.

• Time : O(n)
• Space : O(nm)

c++

class ZigzagIterator {
    queue<pair<vector<int>::iterator, vector<int>::iterator>> q;
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        if(!v1.empty())
            q.push({v1.begin(), v1.end()});

        if(!v2.empty())
            q.push({v2.begin(), v2.end()});
    }

    int next() {
        int res = *q.front().first;
        if(q.front().first + 1 != q.front().second) {
            q.push({q.front().first + 1, q.front().second});
        }
        q.pop();
        return res;
    }

    bool hasNext() {
        return !q.empty();
    }
};

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

• Time : O(nm)
• Space : O(nm)

c++

class ZigzagIterator {
    vector<vector<int>> v;
    int iterator;
    int pos;
    int sz;
    void iterating() {
        for(int i = 0; i < sz; i++) {
            if(v[iterator].size() <= pos)
                iterator = (iterator + 1) % sz;
            else break;
            if(iterator == 0) pos++;
        }
    }
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        v = vector<vector<int>>(2,vector<int>());
        v[0] = v1;
        v[1] = v2;
        iterator = 0;
        pos = 0;
        sz = 2;
        iterating();
    }

    int next() {
        int res = v[iterator][pos];
        iterator = (iterator + 1) % sz;
        if(iterator == 0) pos++;
        iterating();
        return res;
    }

    bool hasNext() {
        return v[iterator].size() > pos;
    }
};

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