Zigzag Iterator - Leetcode Solution

Problem Statement:

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].

Approach:

We can solve this problem using a queue. We will insert the input vectors into a queue and then, we will pop the front of the queue and iteratively return the first element of that vector and then push the remaining elements of that vector at the back of the queue. We will repeat this process until there is no element left in the queue.

Code:

class ZigzagIterator:
    def __init__(self, v1: List[int], v2: List[int]):
        self.q = []
        if v1:
            self.q.append(v1)
        if v2:
            self.q.append(v2)
        
    def next(self) -> int:
        v = self.q.pop(0)
        val = v.pop(0)
        if len(v) > 0:
            self.q.append(v)
        return val

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

Explanation:

We have created a class ZigzagIterator and initialized a queue q. In the constructor, we are checking if v1 and v2 have any elements and then appending them in the queue.

In the next() function, we have popped the front of the queue and then popped the first element of that vector. We have also checked if the length of the vector is greater than 0. If it is, then we are pushing the remaining elements of the vector at the back of the queue. Finally, we are returning the value of the element.

In the hasNext() function, we are checking if the length of the queue is greater than 0. If it is, then we are returning True else False.

Time Complexity:

The time complexity of next() function is O(1) and the time complexity of hasNext() function is also O(1). Therefore, the overall time complexity of the code is O(n), where n is the total number of elements given as an input.

Space Complexity:

The space complexity of the code is also O(n), where n is the total number of elements given as an input. We are using a queue to store the input vectors. In the worst case, we may have to store all the elements in the queue.

1