Skip to content
MediumStacks QueuesAI interview only

Zigzag Iterator

Asked atgooglemetaamazonlinkedinuber

01 · Problem

Design an iterator over two integer lists v1 and v2 that returns their elements alternately, starting with v1: the first element of v1, then the first element of v2, then the second element of v1, and so on. Once one list runs out, the remaining elements of the other list are returned in order.

Implement the ZigzagIterator class:

  • ZigzagIterator(v1, v2) initializes the iterator with the two lists (either may be empty).
  • int next() returns the next element in zigzag order. It is only called when hasNext() would return true.
  • boolean hasNext() returns true if any elements remain, otherwise false.

The input is given as a list of operation names and a list of argument lists; the output lists each operation's return value, with null for the constructor.

02 · Examples

Example 01
Input
["ZigzagIterator","next","next","next","next","hasNext","next","next","hasNext"], [[[1,2],[3,4,5,6]],[],[],[],[],[],[],[],[]]
Output
[null,1,3,2,4,true,5,6,false]

Values come out as 1 (v1), 3 (v2), 2 (v1), 4 (v2); v1 is now exhausted, so 5 and 6 follow from v2. After 6 nothing is left, so hasNext returns false.

Example 02
Input
["ZigzagIterator","hasNext","next","hasNext"], [[[1],[]],[],[],[]]
Output
[null,true,1,false]

Only v1 has data. next returns 1 and then no elements remain.

Example 03
Input
["ZigzagIterator","hasNext"], [[[],[]],[]]
Output
[null,false]

Both lists are empty, so hasNext is false straight away.

03 · Constraints

  • 010 <= v1.length, v2.length <= 1000
  • 02v1.length + v2.length <= 2000 (both lists may be empty)
  • 03-231 <= v1[i], v2[i] <= 231 - 1
  • 04At most 2000 calls will be made to next and hasNext in total

04 · Optimal complexity

Time
O(1) per call
Space
O(k)
05 · Two ways to work on it

Practice it alone or rehearse it as an interview.

Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.

Start a voice interview on this problem