Solutions

1. Two-Pointers

class ZigzagIterator:
    def __init__(self, v1: List[int], v2: List[int]):
        self.vectors = [v1, v2]

        self.p_elem = 0   # pointer to the index of element
        self.p_vec = 0    # pointer to the vector

        # variables for hasNext() function
        self.total_num = len(v1) + len(v2)
        self.output_count = 0

    def next(self) -> int:
        iter_num = 0
        ret = None

        # Iterate over the vectors
        while iter_num < len(self.vectors):
            curr_vec = self.vectors[self.p_vec]
            if self.p_elem < len(curr_vec):
                ret = curr_vec[self.p_elem]

            iter_num += 1
            self.p_vec = (self.p_vec + 1) % len(self.vectors)
            # increment the element pointer once iterating all vectors
            if self.p_vec == 0:
                self.p_elem += 1

            if ret is not None:
                self.output_count += 1
                return ret

        # no more element to output
        raise Exception


    def hasNext(self) -> bool:
        return self.output_count < self.total_num

Time & Space Complexity

Time Complexity:
- For the next() function, at most it will take us $K$ iterations to find a valid element to output. Hence, its time complexity is $O(K)$ .
- For the hasNext() function, its time complexity is $O(1)$ .
Space Complexity:
- For the next() function, we keep the references to all the input vectors in the variable self.vectors.
- As a result, we would need $O(K)$ space for $K$ vectors.
- In addition, we used some constant-space variables such as the pointers to the vector and the element.
- Hence, the overall space complexity for this function is $O(K)$ .
- Note: we did not copy the input vectors, but simply keep references to them.

Where $K$ is the number of input vectors. Although it is always two in the setting of this problem, this variable becomes relevant once the input becomes $K$ vectors.

2. Queue of Pointers

class ZigzagIterator:
    def __init__(self, v1: List[int], v2: List[int]):
        self.vectors = [v1, v2]
        self.queue = deque()
        for index, vector in enumerate(self.vectors):
            # <index_of_vector, index_of_element_to_output>
            if len(vector) > 0:
                self.queue.append((index, 0))

    def next(self) -> int:

        if self.queue:
            vec_index, elem_index = self.queue.popleft()
            next_elem_index = elem_index + 1
            if next_elem_index < len(self.vectors[vec_index]):
                # append the pointer for the next round
                # if there are some elements left
                self.queue.append((vec_index, next_elem_index))

            return self.vectors[vec_index][elem_index]

        # no more element to output
        raise Exception

    def hasNext(self) -> bool:
        return len(self.queue) > 0

Time & Space Complexity

Time Complexity: $O(1)$
- For both the next() function and the hasNext() function, we have a constant time complexity, as we discussed before.
Space Complexity: $O(K)$
- We use a queue to keep track of the pointers to the input vectors in the variable self.vectors.
- As a result, we would need $O(K)$ space for $K$ vectors.
- Although the size of the queue will reduce over time once we exhaust some shorter vectors, the space complexity for both functions is still $O(K)$ .

Where $K$ is the number of input vectors. Although it is always two in the setting of this problem, this variable becomes relevant once the input becomes $K$ vectors.