Problem Description

You need to design an iterator that takes two lists of integers and returns their elements in an alternating pattern (zigzag order).

The iterator should alternate between the two input vectors, returning one element from the first vector, then one from the second vector, then back to the first vector, and so on. When one vector is exhausted, the iterator should continue returning elements from the remaining vector.

The ZigzagIterator class needs three methods:

1. Constructor ZigzagIterator(v1, v2): Initializes the iterator with two integer lists v1 and v2.

2. hasNext(): Returns true if there are still elements to iterate through from either vector, false if both vectors have been completely consumed.

3. next(): Returns the current element and advances the iterator to prepare for the next element. The elements should be returned in alternating order between the two vectors.

For example, if v1 = [1, 2] and v2 = [3, 4, 5, 6], calling next() repeatedly would return: 1, 3, 2, 4, 5, 6.

The solution uses a circular approach with:

• cur: tracks which vector to read from next (0 or 1)
• indexes: maintains the current position in each vector
• vectors: stores references to both input vectors

The hasNext() method checks if there are remaining elements by cycling through vectors until it finds one with unread elements or determines all vectors are exhausted. The next() method retrieves the current element, updates the index for that vector, and moves to the next vector in round-robin fashion.

Intuition

The key insight is to think of this problem as a round-robin scheduling scenario. When we need to alternate between two lists, we're essentially taking turns - first from list 1, then from list 2, then back to list 1, and so on.

To implement this "taking turns" behavior, we can use a pointer that cycles through the vectors in order. Think of it like dealing cards from multiple decks - you deal one card from deck 1, then one from deck 2, then back to deck 1. The dealer's hand moves in a circular pattern between the decks.

We need to track our position in each vector independently because they might have different lengths. This is why we maintain separate indexes for each vector - when we return to a vector after visiting the other one, we need to know where we left off.

The challenge comes when one vector runs out of elements before the other. In a naive alternating approach, we might try to access an element that doesn't exist. To handle this elegantly, when we encounter an exhausted vector during our round-robin cycle, we simply skip it and move to the next one. This is like a card dealer skipping an empty deck and continuing with the remaining decks.

The modulo operation (cur + 1) % size gives us the circular behavior naturally - after vector 1 (index 1), we wrap back to vector 0. This pattern extends beautifully if we wanted to support more than two vectors.

For hasNext(), we need to check if any vector still has elements. We start from our current position and cycle through all vectors. If we make a complete circle back to where we started without finding any remaining elements, we know the iteration is complete. This circular checking ensures we don't miss any remaining elements in vectors we haven't checked yet.

Solution Approach

The implementation uses a round-robin pattern with index tracking for each vector. Let's break down the key components and methods:

Data Structure Setup:

• self.cur = 0: Maintains which vector (0 or 1) we should read from next
• self.size = 2: The number of vectors we're alternating between
• self.indexes = [0] * self.size: An array tracking the current reading position in each vector (initially all zeros)
• self.vectors = [v1, v2]: Stores references to both input vectors for easy access

next() Method Implementation:

1. Get the current vector using self.vectors[self.cur]
2. Get the current index position for this vector using self.indexes[self.cur]
3. Retrieve the element at vector[index] and store it as the result
4. Increment the index for this vector: self.indexes[self.cur] = index + 1
5. Move to the next vector in round-robin fashion: self.cur = (self.cur + 1) % self.size
6. Return the retrieved element

The modulo operation ensures we cycle back to vector 0 after vector 1, creating the alternating pattern.

hasNext() Method Implementation:

1. Remember the starting position: start = self.cur
2. Enter a loop to find a vector with remaining elements:
   • Check if the current vector is exhausted: self.indexes[self.cur] == len(self.vectors[self.cur])
   • If exhausted, move to the next vector: self.cur = (self.cur + 1) % self.size
   • If we've cycled through all vectors and returned to the start position, return False (no elements left)
3. If we find a vector with remaining elements, return True

The clever part of hasNext() is that it automatically positions self.cur at the next valid vector. This means when next() is called, it's guaranteed to find an element at the current position. This pre-positioning eliminates the need for additional checking in the next() method.

Time Complexity:

• next(): O(1) - direct array access and simple arithmetic operations
• hasNext(): O(k) where k is the number of vectors (in this case, k=2, so effectively O(1))

Space Complexity: O(1) additional space beyond storing the input vectors (we only maintain a few integer variables and references)

Example Walkthrough

Let's walk through an example with v1 = [1, 2] and v2 = [3, 4, 5].

Initial State:

• cur = 0 (start with vector 0)
• indexes = [0, 0] (both vectors start at position 0)
• vectors = [[1, 2], [3, 4, 5]]

Operation 1: hasNext()

• Check if indexes[0] == len(vectors[0]) → 0 == 2? No
• Return True (vector 0 has elements)
• cur remains at 0

Operation 2: next()

• Access vectors[0][indexes[0]] → vectors[0][0] = 1
• Update indexes[0] from 0 to 1
• Move cur to (0 + 1) % 2 = 1
• Return 1

Operation 3: next()

• Access vectors[1][indexes[1]] → vectors[1][0] = 3
• Update indexes[1] from 0 to 1
• Move cur to (1 + 1) % 2 = 0
• Return 3

Operation 4: next()

• Access vectors[0][indexes[0]] → vectors[0][1] = 2
• Update indexes[0] from 1 to 2
• Move cur to (0 + 1) % 2 = 1
• Return 2

Operation 5: hasNext()

• Start at cur = 1
• Check if indexes[1] == len(vectors[1]) → 1 == 3? No
• Return True (vector 1 has elements)
• cur remains at 1

Operation 6: next()

• Access vectors[1][indexes[1]] → vectors[1][1] = 4
• Update indexes[1] from 1 to 2
• Move cur to (1 + 1) % 2 = 0
• Return 4

Operation 7: hasNext()

• Start at cur = 0
• Check if indexes[0] == len(vectors[0]) → 2 == 2? Yes (vector 0 exhausted)
• Move cur to (0 + 1) % 2 = 1
• Check if indexes[1] == len(vectors[1]) → 2 == 3? No
• Return True (vector 1 still has elements)
• cur stays at 1 (positioned at next valid vector)

Operation 8: next()

• Access vectors[1][indexes[1]] → vectors[1][2] = 5
• Update indexes[1] from 2 to 3
• Move cur to (1 + 1) % 2 = 0
• Return 5

Operation 9: hasNext()

• Start at cur = 0
• Check if indexes[0] == len(vectors[0]) → 2 == 2? Yes (vector 0 exhausted)
• Move cur to (0 + 1) % 2 = 1
• Check if indexes[1] == len(vectors[1]) → 3 == 3? Yes (vector 1 exhausted)
• Move cur to (1 + 1) % 2 = 0
• We've cycled back to start position 0, all vectors exhausted
• Return False

Final output sequence: 1, 3, 2, 4, 5

The algorithm successfully alternates between vectors until one is exhausted, then continues with the remaining vector.

Solution Implementation

Time and Space Complexity

Time Complexity:

• __init__: O(1) - The initialization only involves setting up a few variables and storing references to the input vectors. No iteration or copying is performed.
• next(): O(1) - This method performs constant-time operations: accessing an element from a vector by index, incrementing an index, and updating the current pointer using modulo operation.
• hasNext(): O(k) in the worst case, where k is the number of vectors (in this case k = 2). The method may need to cycle through all vectors once to find a non-exhausted vector or determine that all vectors are exhausted. Since k = 2 is constant here, this is effectively O(1).

Space Complexity:

• O(1) extra space - The iterator only maintains:

  • self.cur: a single integer for the current vector index
  • self.size: a constant integer (always 2)
  • self.indexes: an array of size 2 to track current positions
  • self.vectors: stores references to the input vectors (not copies)

  Since the iterator stores only references to the original vectors rather than copying them, and maintains a fixed-size array of indices regardless of input size, the extra space used is constant O(1). The input vectors themselves take O(n + m) space where n and m are the lengths of v1 and v2, but this is not counted as extra space used by the iterator.

Common Pitfalls

1. Not Handling Empty Vectors Properly

A critical pitfall is failing to handle cases where one or both input vectors are empty from the start. If v1 = [] and v2 = [1, 2, 3], the iterator should seamlessly skip the empty vector and return elements from v2.

Problem Example:

# Without proper handling, this could cause issues:
v1 = []
v2 = [1, 2, 3]
iterator = ZigzagIterator(v1, v2)
# Calling next() might try to access v1[0] which doesn't exist

Solution: The current implementation handles this correctly through the hasNext() method which automatically skips exhausted (including initially empty) vectors. However, you should ensure hasNext() is always called before next() to guarantee safe operation.

2. Modifying self.cur in hasNext() Without Restoration

The hasNext() method modifies the state by changing self.cur to position it at the next valid vector. This is actually intentional design, but it can be confusing because typically a "check" method shouldn't modify state.

Problem Example:

# Calling hasNext() multiple times changes internal state
iterator = ZigzagIterator([1], [2])
print(iterator.hasNext())  # True, cur might be 0
print(iterator.hasNext())  # True, but cur might have changed
print(iterator.hasNext())  # True, cur keeps changing

Solution: This is actually correct behavior for this implementation pattern. The key insight is that hasNext() serves dual purpose:

1. Checks if elements remain
2. Positions the iterator at the next valid vector

Just be aware that calling hasNext() multiple times without calling next() is safe but may change internal positioning.

3. Infinite Loop in hasNext() When All Vectors Are Empty

If both vectors are empty from the start, the while loop in hasNext() could potentially create an infinite loop if not implemented carefully.

Problem Example:

v1 = []
v2 = []
iterator = ZigzagIterator(v1, v2)
# The while loop needs proper termination condition

Solution: The implementation correctly handles this with the cycle detection:

if self.current_vector_index == start_index:
    return False

This ensures we only check each vector once and exit if we return to the starting position.

4. Assuming Equal-Length Vectors

A common mistake is writing code that assumes both vectors have the same length or that they'll exhaust simultaneously.

Problem Example:

# Wrong assumption: alternating until both are empty
v1 = [1, 2]
v2 = [3, 4, 5, 6, 7, 8]
# Must continue with v2 after v1 is exhausted

Solution: The current implementation correctly handles unequal lengths by:

• Continuing to check both vectors in round-robin fashion
• Skipping exhausted vectors automatically
• Returning remaining elements from the non-exhausted vector

5. Not Preserving Round-Robin Order After Exhaustion

When one vector is exhausted, some implementations might stick to the remaining vector immediately. However, the correct behavior maintains the round-robin checking pattern.

Problem Example:

v1 = [1, 2, 3]
v2 = [4]
# After returning 1, 4, should return 2 (not immediately exhaust v1)
# Correct order: 1, 4, 2, 3

Solution: The modulo arithmetic (self.current_vector_index + 1) % self.num_vectors ensures we always attempt to alternate, and hasNext() skips over exhausted vectors while maintaining the pattern.