281. Zigzag Iterator

Posted on Edited on In

281. Zigzag Iterator

Description

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.

Example 1:

1
2
3
Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].

Example 2:

1
2
Input: v1 = [1], v2 = []
Output: [1]

Example 3:

1
2
Input: v1 = [], v2 = [1]
Output: [1]

Constraints:

  • 0 <= v1.length, v2.length <= 1000
  • 1 <= v1.length + v2.length <= 2000
  • -2^31 <= v1[i], v2[i] <= 2^31 - 1

Follow up: What if you are given k vectors? How well can your code be extended to such cases?

Clarification for the follow-up question:

The “Zigzag” order is not clearly defined and is ambiguous for k > 2 cases. If “Zigzag” does not look right to you, replace “Zigzag” with “Cyclic”.

Follow-up Example:

1
2
Input: v1 = [1,2,3], v2 = [4,5,6,7], v3 = [8,9]
Output: [1,4,8,2,5,9,3,6,7]

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class ZigzagIterator {
public:
    queue<pair<int, int>> q;
    vector<vector<int>> v;
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        v.push_back(v1);
        v.push_back(v2);
        for (int i = 0; i < v.size(); i++) {
            if (v[i].size()) {
                q.push({i, 0});
            }
        }
    }

    int next() {
        auto [vIdx, idx] = q.front();
        q.pop();
        int res = v[vIdx][idx];
        idx++;
        if (v[vIdx].size() > idx) {
            q.emplace(vIdx, idx);
        }
        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();
 */