/**
* 281. Zigzag Iterator Given two 1d vectors, implement an iterator to return their elements alternately.
* Example:
* <p>
* 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].
*/
See the solution to the problem at github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/ZigZagIterator.java
Observation: The problem asks us to alternatively return elements from two lists while adhering to the iterator interface. And when one list has been completely iterated over, it should be skipped.
The solution can be implemented via creating a list of lists and one by one iterating over the lists. For each list the current index can be kept in an array.
While the question asks us to work with two arrays, this implementation can easily be modified to work over n arrays.
See the code here:
//index to the current list in array that is being processed
int currIndex = 0;
//lists to be processed
List<List<Integer>> lists;
//list of current indexes for each of the lists
Integer[] listIndexes;
public ZigZagIterator(List<Integer> v1, List<Integer> v2) {
int count = 2;
lists = new ArrayList<> ();
lists.add(v1);
lists.add(v2);
listIndexes = new Integer[count];
for (int i = 0; i < count; i++) {
listIndexes[i] = 0;
}
}
/**
* if the index or the element at current list is at end, move to the next list output the element in curr list and
* move its index ahead
*/
public int next() {
while (listIndexes[currIndex] == lists.get(currIndex).size()) {
currIndex = getNextIndex();
}
int val = lists.get(currIndex).get(listIndexes[currIndex]);
listIndexes[currIndex] = listIndexes[currIndex] + 1;
currIndex = getNextIndex();
return val;
}
/**
* return true if any of the lists has a next element available
*/
public boolean hasNext() {
int iterations = 0;
while (listIndexes[currIndex] == lists.get(currIndex).size() && iterations != listIndexes.length) {
currIndex = getNextIndex();
iterations++;
}
return listIndexes[currIndex] != lists.get(currIndex).size();
}
/**
* internal helper method to get next list
*/
int getNextIndex() {
return (currIndex + 1) % lists.size();
}