LeetCode 281: Zigzag Iterator Solution

Master LeetCode problem 281 (Zigzag Iterator), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

281. Zigzag Iterator

Medium

Array Design Queue Iterator

Problem Explanation

Explanation

To implement a Zigzag Iterator, we can use a queue to store the iterators of the given lists. We will iterate through each list in a round-robin manner, getting elements from each list in turn until all elements are exhausted.

Initialize a queue to store the iterators of the given lists.
Add non-empty lists' iterators to the queue.
While the queue is not empty, pop an iterator from the front of the queue, get the next element from it, and add the iterator back to the queue if it has more elements.
Repeat step 3 until all iterators are exhausted.

Time Complexity

Initialization: O(n), where n is the number of lists.
Getting next element: O(1) on average.
Overall time complexity: O(N) where N is the total number of elements across all lists.

Space Complexity

O(n) where n is the number of lists.

Solution Code

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class ZigzagIterator {
    private Queue<Iterator<Integer>> queue;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        queue = new LinkedList<>();
        if (!v1.isEmpty()) {
            queue.offer(v1.iterator());
        }
        if (!v2.isEmpty()) {
            queue.offer(v2.iterator());
        }
    }

    public int next() {
        Iterator<Integer> iter = queue.poll();
        int result = iter.next();
        if (iter.hasNext()) {
            queue.offer(iter);
        }
        return result;
    }

    public boolean hasNext() {
        return !queue.isEmpty();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 281 (Zigzag Iterator)?

This page provides optimized solutions for LeetCode problem 281 (Zigzag Iterator) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 281 (Zigzag Iterator)?

The time complexity for LeetCode 281 (Zigzag Iterator) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 281 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 281 in Java, C++, or Python.

Back to LeetCode Solutions