Vultr DocsLatest Content

Zigzag Iterator

Updated on 03 July, 2025
Zigzag Iterator header image

Problem Statement

In this task, you are given two integer vectors, v1 and v2. Your goal is to create a custom iterator named ZigzagIterator that traverses these two vectors alternately. The specifics of the iterator class include one constructor and two methods:

  1. ZigzagIterator(List<int> v1, List<int> v2) - This constructor takes two integer vectors and prepares them for alternate traversal.
  2. boolean hasNext() - This method checks if there are any more elements left to traverse in either of the vectors. It returns true if there are elements left to iterate; otherwise, it returns false.
  3. int next() - This returns the current element of the iteration sequence and moves the pointer or indicator to the following element.

The aim is to traverse through the elements of both vectors in a zigzag or alternating manner, starting with the first element of the first vector if it is non-empty.

Examples

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]

Explanation:

Since v2 is empty, the iterator just returns the elements from v1.

Example 3

Input:

v1 = [], v2 = [1]

Output:

[1]

Explanation:

Since v1 is empty, elements from v2 are used.

Constraints

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

Approach and Intuition

The ZigzagIterator must alternate between two vectors, returning elements from each. Depending on the lengths of v1 and v2, one can be exhausted before the other, after which elements should be returned from the remaining vector until no more elements are available.

Steps for Implementing ZigzagIterator

  1. Initialization: Create two pointers, one for each vector, and a variable to track which vector's turn it is.

  2. hasNext(): Check whether either pointer has not yet reached the end of its corresponding vector.

  3. next():

    • If both vectors have remaining elements, alternate turns between them.
    • If one vector is exhausted, continue returning elements from the remaining one.
    • After returning an element, update the pointer and toggle the turn if both still have elements.

This approach ensures the iterator returns elements in a zigzag fashion until one vector is exhausted and then continues linearly with the remaining vector.

Solutions

  • Java
java 
public class IteratorZigzag {
    private List<List<Integer>> dataLists = new ArrayList<>();
    private Queue<Pair<Integer, Integer>> elementQueue = new LinkedList<>();
    
    public IteratorZigzag(List<Integer> firstList, List<Integer> secondList) {
        this.dataLists.add(firstList);
        this.dataLists.add(secondList);
        int index = 0;
        for (List<Integer> list : this.dataLists) {
            if (!list.isEmpty())
                // Add index pair <list_index, element_index>
                this.elementQueue.offer(new Pair<>(index, 0));
            index++;
        }
    }
    
    public int next() {
        Pair<Integer, Integer> indexPair = this.elementQueue.poll();
        Integer listIndex = indexPair.getKey();
        Integer elementIndex = indexPair.getValue();
        Integer nextElementIndex = elementIndex + 1;
        // Check if there's more elements in the current list
        if (nextElementIndex < this.dataLists.get(listIndex).size())
            this.elementQueue.add(new Pair<>(listIndex, nextElementIndex));
    
        return this.dataLists.get(listIndex).get(elementIndex);
    }
    
    public boolean hasNext() {
        return !this.elementQueue.isEmpty();
    }
}

The given Java code implements a Zigzag Iterator for two lists of integers. It manages iteration across the two lists by alternating elements from each list using a queue.

  • Initialize IteratorZigzag with two lists: firstList and secondList. These lists are stored in the dataLists ArrayList.

  • The constructor populates a queue, elementQueue, using pairs that track which list and which element within that list should be accessed next. It checks for non-empty lists and queues up the first element's index of each non-empty list.

  • The next() method processes elements in the zigzag order:

    • It removes the top pair from the queue to get the current list and element indices.
    • If more elements are available in the same list, it queues up the next element's index.
    • The method finally returns the integer value of the current element.

  • The hasNext() function serves a straightforward purpose: it checks if there are any more elements to process by returning whether the elementQueue is empty or not.

This approach allows for zigzag traversal over two lists, effectively merging their elements in an alternate fashion while accommodating differences in their lengths.

  • Python
python 
class AlternatingIterator:
    def __init__(self, list1: List[int], list2: List[int]):
        self.data = [list1, list2]
        self.process_queue = deque()
        for idx, lst in enumerate(self.data):
            if lst:
                self.process_queue.append((idx, 0))
    
    def next(self) -> int:
        if self.process_queue:
            list_index, item_index = self.process_queue.popleft()
            next_item_index = item_index + 1
            if next_item_index < len(self.data[list_index]):
                self.process_queue.append((list_index, next_item_index))
    
            return self.data[list_index][item_index]
    
        raise Exception("No more elements.")
    
    def hasNext(self) -> bool:
        return bool(self.process_queue)

Explore the provided Python class, AlternatingIterator, designed to iterate alternately over two integer lists. This solution uses a combination of lists and a deque from the collections module to facilitate alternate iteration, crucial for creating an efficient zigzag pattern.

  • Construct an instance initialization with two arguments, list1 and list2. These are stored internally, and a process queue is established to track the position in each list for alternating access.

  • Implement the next() method:

    • This method confirms the presence of elements in the process queue.
    • It then retrieves and removes the front element of this queue, consisting of the current list and element indices.
    • If subsequent elements exist in the respective list, their positions are pushed back onto the queue, ensuring continued alternating access.
    • Finally, it returns the relevant element of the current list based on the stored index. If the queue is empty, it raises an exception signaling no more elements.

  • The hasNext() method simply checks if there are any remaining items in the process queue.

By initializing with two lists and executing methods to alternate between them, one achieves an efficient and controlled iteration over two sequences in a zigzag manner. The use of a process queue helps in managing state over multiple calls, making the iterator versatile for potentially extended sequences or integration into more complex data processing flows.

Comments

No comments yet.