How hard is LeetCode 281. Zigzag Iterator?

LeetCode 281. Zigzag Iterator is rated Medium on LeetCode.

What is the time complexity of LeetCode 281. Zigzag Iterator?

The Python solution on this page runs in O(V+E).

What is the space complexity of LeetCode 281. Zigzag Iterator?

The Python solution on this page uses O(V) auxiliary space.

What topics does LeetCode 281. Zigzag Iterator cover?

LeetCode 281. Zigzag Iterator is tagged Design, Queue, Array and Iterator on LeetCode.

Is LeetCode 281. Zigzag Iterator a premium problem?

Yes. LeetCode 281. Zigzag Iterator is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.

Zigzag Iterator — LeetCode 281 Python Solution

MediumLeetCode PremiumDesignQueueArrayIterator

Problem: #281
Pattern: Stack
Reading time: 5 min
Source: leetcode.com

The problem

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.

Example

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

Python solution

Python

class ZigzagIterator:
    def __init__(self, v1: List[int], v2: List[int]):
        self.cur = 0
        self.size = 2
        self.indexes = [0] * self.size
        self.vectors = [v1, v2]

    def next(self) -> int:
        vector = self.vectors[self.cur]
        index = self.indexes[self.cur]
        res = vector[index]
        self.indexes[self.cur] = index + 1
        self.cur = (self.cur + 1) % self.size
        return res

    def hasNext(self) -> bool:
        start = self.cur
        while self.indexes[self.cur] == len(self.vectors[self.cur]):
            self.cur = (self.cur + 1) % self.size
            if self.cur == start:
                return False
        return True


# Your ZigzagIterator object will be instantiated and called as such:
# i, v = ZigzagIterator(v1, v2), []
# while i.hasNext(): v.append(i.next())

Complexity

Measure	Complexity
Time	O(V+E)
Space	O(V) auxiliary

Pattern: Stack

When the most recent unresolved thing is the one that matters, use a stack. LeetCode 281. Zigzag Iterator is filed here because LeetCode tags it Queue, which is the vocabulary this hub collects.

The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 281. Zigzag Iterator?: LeetCode 281. Zigzag Iterator is rated Medium on LeetCode.
What is the time complexity of LeetCode 281. Zigzag Iterator?: The Python solution on this page runs in O(V+E).
What is the space complexity of LeetCode 281. Zigzag Iterator?: The Python solution on this page uses O(V) auxiliary space.
What topics does LeetCode 281. Zigzag Iterator cover?: LeetCode 281. Zigzag Iterator is tagged Design, Queue, Array and Iterator on LeetCode.
Is LeetCode 281. Zigzag Iterator a premium problem?: Yes. LeetCode 281. Zigzag Iterator is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.