LC: 281. Zigzag Iterator

https://leetcode.com/problems/zigzag-iterator/

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 <= 1000
1 <= 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".

Example:

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

Details:

The list and index pointers can just be integers, with the list pointer going back and forth between 0 and 1. The index pointer should increase when an element is returned, or when hasNext is called.

For the follow-up problem of extending the algorithm to multiple list, one can use queue for prioritizing the lists or keep which sets are exhausted in an array or a set.

Solutions: https://github.com/spiralgo/algorithms/tree/master/src/main/java/algorithms/curated170/medium/zigzagiterator

Default Code:

public class ZigzagIterator {

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        
    }

    public int next() {
        
    }

    public boolean hasNext() {
        
    }
}

/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator i = new ZigzagIterator(v1, v2);
 * while (i.hasNext()) v[f()] = i.next();
 */

PreviousLC: 280. Wiggle Sort NextLC: 296. Best Meeting Point

Last updated 3 years ago