We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Zigzag Iterator

Number: 281

Difficulty: Medium

Paid? Yes

Companies: Coinbase, Google

Problem Description

Design an iterator that alternates (or "zigzags") between two given vectors. For the basic version, given two lists of integers (v1 and v2), the iterator should return elements one by one from each list in turn (i.e., first element of v1, then first element of v2, then second element of v1, etc.). When one list is exhausted, continue iterating over the remaining elements of the other list. Additionally, consider how this can be extended to k vectors following the same cyclic order.

Key Insights

  • Use a FIFO (first-in-first-out) structure to maintain the order of vectors which still have remaining elements.
  • For each call to next(), select the next element from the current vector and then move that vector to the end of the queue if it still contains elements.
  • The approach ensures proper zigzag (or cyclic) ordering among the vectors.
  • When extending to k vectors, the same approach works: initialize the queue with each non-empty vector.

Space and Time Complexity

Time Complexity: O(1) per next() call on average, with an overall O(n) for n total elements. Space Complexity: O(k) for the queue structure (where k is the number of vectors), plus the storage for the input vectors.

Solution

We can solve the Zigzag Iterator problem by using a queue (or deque) to hold pairs of the vector’s current index and the vector itself. For each call to next(), we remove the front element from the queue, return the current item from its associated vector, and if the vector has more elements, reinsert the pair (with an updated index) into the back of the queue. This cyclic process naturally interleaves the elements from the provided vectors.

Code Solutions

class ZigzagIterator:
    def __init__(self, v1, v2):
        # Initialize the queue with non-empty vectors paired with starting index 0
        from collections import deque
        self.queue = deque()
        if v1:
            self.queue.append((v1, 0))
        if v2:
            self.queue.append((v2, 0))

    def next(self):
        # Pop from the left
        vec, idx = self.queue.popleft()
        result = vec[idx]
        # If there are more elements, put it back with the next index
        if idx + 1 < len(vec):
            self.queue.append((vec, idx + 1))
        return result

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

# Example usage:
# v1 = [1,2]; v2 = [3,4,5,6]
# iterator = ZigzagIterator(v1, v2)
# while iterator.hasNext():
#     print(iterator.next(), end=" ")
← Back to All Questions