# 281. Zigzag Iterator
Given two 1d vectors, implement an iterator to return their elements alternately.
Example:
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].
Follow up: What if you are given k 1d 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". For example:
Input:
[1,2,3]
[4,5,6,7]
[8,9]
Output: [1,4,8,2,5,9,3,6,7].
# Solution
Approach 1: for the follow up generalization, store iterators in a queue.
# Code (Python)
Approach 1:
# An wrapper implementation in Python with next() and has_next() methods
# In native python you need to implement __iter__() returning self, and __next__() returning the next element or raise StopIteration
class Iterator:
def __init__(self, iterable):
self._iterator = iter(iterable)
self._test_next()
def _test_next(self):
try:
self._next_val = next(self._iterator)
self._has_next = True
except StopIteration as e:
self._next_val = None
self._has_next = False
def next(self):
if self._has_next:
val = self._next_val
self._test_next()
return val
else:
raise StopIteration()
def has_next(self):
return self._has_next
# actual ZigzagIterator implementation
from collections import deque
class ZigzagIterator():
def __init__(self, lists):
self._queue = deque([Iterator(item) for item in lists])
self._has_next = False
self._next = None
self._set_next()
def _set_next(self):
# get next item
while self._queue:
iterator = self._queue.popleft()
if iterator.has_next():
self._next = iterator.next()
self._has_next = True
self._queue.append(iterator)
return
self._next = None
self._has_next = False
def next(self):
if self._has_next:
val = self._next
self._set_next()
return val
else:
raise StopIteration()
def has_next(self):
return self._has_next
it = ZigzagIterator([[1,3,5], [2, 4], [100], []])
while it.has_next():
print(it.next())
# Code (C++)
Approach 1:
Approach 2: