Given two vectors of integers v1 and v2, implement an iterator to return their elements alternately.
Implement the ZigzagIterator class:
ZigzagIterator(List<int> v1, List<int> 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:
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:
Input: v1 = [1], v2 = [] Output: [1]
Example 3:
Input: v1 = [], v2 = [1] Output: [1]
Constraints:
0 <= v1.length, v2.length <= 10001 <= v1.length + v2.length <= 2000-231 <= v1[i], v2[i] <= 231 - 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:
Input: v1 = [1,2,3], v2 = [4,5,6,7], v3 = [8,9] Output: [1,4,8,2,5,9,3,6,7]
Problem Overview: You receive two integer arrays and must iterate through them in alternating order. The iterator should return elements like v1[0], v2[0], v1[1], v2[1] and continue until both arrays are exhausted.
Approach 1: Pointer + Turn Simulation (O(n) time, O(1) space)
Maintain two indices i and j for the arrays and a boolean flag indicating whose turn it is. On each call to next(), return the element from the current array if it still has elements; otherwise switch to the other array. The iterator advances the corresponding pointer after returning a value. This works because the arrays are accessed sequentially, but the logic becomes messy when one array finishes earlier and the turn flag must be skipped repeatedly.
Approach 2: Queue of Iterators (O(n) time, O(k) space)
Store active iterators in a queue. Initially push iterators for both arrays if they are non‑empty. When next() is called, pop the front iterator, return its next element, and push it back if it still has remaining elements. This naturally rotates between arrays and automatically handles uneven lengths. The queue size is at most k (number of arrays), which is 2 in this problem but generalizes easily.
The key insight: alternating order is essentially round‑robin scheduling. A queue perfectly models this behavior. Each iterator gets one turn, then moves to the back until it runs out of elements.
This design approach is common in iterator problems and appears in tasks involving cyclic traversal or multi-source iteration. Understanding how to manage state with a queue and implement a custom iterator interface is the main learning goal. The input itself is just an array, but the challenge is designing a clean iteration mechanism.
Recommended for interviews: The queue-of-iterators solution is the expected answer. It keeps the code clean, avoids complicated condition checks, and generalizes to more than two arrays. Mentioning the pointer simulation approach first shows you understand the basic mechanics, but implementing the queue-based iterator demonstrates stronger design skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pointer + Turn Simulation | O(n) | O(1) | Simple cases with only two arrays and minimal abstraction needed |
| Queue of Iterators (Round Robin) | O(n) | O(k) | Preferred design approach; clean logic and easily extends to multiple arrays |
281. Zigzag Iterator • Muerde un zombie • 1,461 views views
Watch 9 more video solutions →Practice Zigzag Iterator with our built-in code editor and test cases.
Practice on FleetCode