Skip to main content
Talentd

Zigzag Iterator - Solution & Explanation

MediumPremiumFree on FleetCodeArrayDesignQueueIterator6 min readAsked at: Amazon, Coinbase, Google +2
Practice this problem

Problem Statement

Given two vectors of integers v1 and v2, implement an iterator to return their elements alternately.

Implement the ZigzagIterator class:

  • ZigzagIterator(List<int> v1, List<int> v2) initializes the object with the two vectors v1 and v2.
  • boolean hasNext() returns true if the iterator still has elements, and false otherwise.
  • int next() returns the current element of the iterator and moves the iterator to the next element.

 

Example 1:

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

Example 2:

Input: v1 = [1], v2 = []
Output: [1]

Example 3:

Input: v1 = [], v2 = [1]
Output: [1]

 

Constraints:

  • 0 <= v1.length, v2.length <= 1000
  • 1 <= v1.length + v2.length <= 2000
  • -231 <= v1[i], v2[i] <= 231 - 1

 

Follow up: What if you are given k vectors? How well can your code be extended to such cases?

Clarification for the follow-up question:

The "Zigzag" order is not clearly defined and is ambiguous for k > 2 cases. If "Zigzag" does not look right to you, replace "Zigzag" with "Cyclic".

Follow-up Example:

Input: v1 = [1,2,3], v2 = [4,5,6,7], v3 = [8,9]
Output: [1,4,8,2,5,9,3,6,7]

Approach Overview

Problem Overview: You receive two integer arrays and must iterate through them in alternating order. The iterator should return elements like v1[0], v2[0], v1[1], v2[1] and continue until both arrays are exhausted.

Approach 1: Pointer + Turn Simulation (O(n) time, O(1) space)

Maintain two indices i and j for the arrays and a boolean flag indicating whose turn it is. On each call to next(), return the element from the current array if it still has elements; otherwise switch to the other array. The iterator advances the corresponding pointer after returning a value. This works because the arrays are accessed sequentially, but the logic becomes messy when one array finishes earlier and the turn flag must be skipped repeatedly.

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

Store active iterators in a queue. Initially push iterators for both arrays if they are non‑empty. When next() is called, pop the front iterator, return its next element, and push it back if it still has remaining elements. This naturally rotates between arrays and automatically handles uneven lengths. The queue size is at most k (number of arrays), which is 2 in this problem but generalizes easily.

The key insight: alternating order is essentially round‑robin scheduling. A queue perfectly models this behavior. Each iterator gets one turn, then moves to the back until it runs out of elements.

This design approach is common in iterator problems and appears in tasks involving cyclic traversal or multi-source iteration. Understanding how to manage state with a queue and implement a custom iterator interface is the main learning goal. The input itself is just an array, but the challenge is designing a clean iteration mechanism.

Recommended for interviews: The queue-of-iterators solution is the expected answer. It keeps the code clean, avoids complicated condition checks, and generalizes to more than two arrays. Mentioning the pointer simulation approach first shows you understand the basic mechanics, but implementing the queue-based iterator demonstrates stronger design skills.

Solution

Code

PythonJavaGoRust

Python

Java

Go

Rust

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Pointer + Turn SimulationO(n)O(1)Simple cases with only two arrays and minimal abstraction needed
Queue of Iterators (Round Robin)O(n)O(k)Preferred design approach; clean logic and easily extends to multiple arrays

Video Solution

281. Zigzag Iterator • Muerde un zombie • 1,474 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Zigzag Iterator easy or hard?
Zigzag Iterator is rated Medium difficulty. The iteration itself is simple, but designing a clean iterator interface and handling uneven array lengths correctly requires careful state management.
Zigzag Iterator Python/Java solution
Python and Java implementations typically store iterators or index pairs inside a queue. The next() method pops the front iterator, returns the next value, and re-enqueues it if elements remain. This keeps the iteration logic concise and efficient.
How to solve Zigzag Iterator in O(n)?
Use a queue that stores iterators or index references for each array. Pop the front iterator, output its next element, and push it back if more elements remain. Since each element is visited exactly once and queue operations are constant time, the solution runs in O(n).
What is the best approach for Zigzag Iterator?
The queue-of-iterators approach is the most robust solution. Maintain a queue containing iterators for each array. Each call to next() pops the front iterator, returns its value, and pushes it back if more elements remain. This achieves O(n) total time and O(k) space where k is the number of arrays.
Is Zigzag Iterator asked at Google/Amazon/Meta?
Zigzag Iterator has appeared in interviews at companies like Google and Meta, especially in roles focused on data structures and system design fundamentals. It evaluates understanding of iterators, queues, and clean state management.
What data structure is used in Zigzag Iterator?
A queue is the primary data structure used in the optimal solution. It maintains the order of active iterators and enables round-robin traversal. Arrays store the input values, while the queue controls the iteration sequence.
What is the time complexity of Zigzag Iterator?
The overall time complexity is O(n), where n is the total number of elements across both arrays. Each element is processed exactly once, and queue operations like push and pop are O(1). Space complexity is O(k) for storing active iterators.

Ready to solve this problem?

Practice Zigzag Iterator with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Search Tree Iterator

Next

Flatten 2D Vector