Zigzag Iterator - Video Solutions

Problem Overview: Design an iterator that returns elements from two input arrays in alternating order. If one array runs out of elements, the iterator continues with the remaining array. The class must support next() and hasNext() operations while preserving the zigzag order.

Approach 1: Pre-build Zigzag Array (O(n) time, O(n) space)

The simplest approach builds the entire zigzag order during initialization. Maintain two indices for the input arrays and alternate inserting elements into a result list. Continue until both arrays are exhausted. The next() call simply returns the next element from the precomputed list while hasNext() checks the index against the list length.

This works because all ordering decisions are made upfront. The tradeoff is memory usage since the entire result is stored even if the caller only consumes part of the iterator. The approach uses basic Array traversal and is straightforward but not ideal when the iterator should behave lazily.

Approach 2: Two Pointers with Toggle (O(n) time, O(1) space)

Track two indices and a flag indicating which array should produce the next value. Each call to next() checks the flag, returns the corresponding element, and advances the pointer. If one array is already exhausted, the logic falls back to the other array. The toggle flips only when both arrays still have elements.

This avoids building an extra list and uses constant memory. However, the logic becomes messy if the problem generalizes to more than two lists. Handling edge cases when one pointer reaches the end requires careful checks. The approach still relies on simple array indexing but lacks extensibility.

Approach 3: Queue of Iterators (O(n) time, O(k) space)

The most flexible design stores iterators in a queue. Initially push an iterator for each non-empty array. When next() is called, pop the front iterator, retrieve its next value, and push it back if it still has elements. This creates the zigzag behavior naturally because iterators rotate through the queue.

The key insight is treating each array iterator as a producer. After consuming one value, the iterator goes to the back of the queue, allowing the next iterator to run. This pattern generalizes cleanly to any number of arrays and matches typical design interview problems involving cyclic iteration. Time complexity is O(n) since each element is processed once, and space complexity is O(k) where k is the number of active iterators.

Recommended for interviews: The queue-of-iterators approach is what interviewers usually expect. It demonstrates clean iterator design and scales naturally to more than two lists. Mentioning the pre-build approach shows you understand the brute-force option, but implementing the queue rotation solution signals strong design thinking.