LeetCode: Zigzag Iterator Posted on August 26, 2019July 26, 2020 by braindenny Zigzag Iterator Similar Problems: CheatSheet: Leetcode For Code Interview CheatSheet: Common Code Problems & Follow-ups Tag: #iterator, #zigzag Given two 1d vectors, implement an iterator to return their elements alternately. 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]. Follow up: What if you are given k 1d 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”. For example: Input: [1,2,3] [4,5,6,7] [8,9] Output: [1,4,8,2,5,9,3,6,7]. Github: code.dennyzhang.com Credits To: leetcode.com Leave me comments, if you have better ways to solve. Solution: Use queue ## https://code.dennyzhang.com/zigzag-iterator ## Basic Ideas: array ## ## Complexity: Time O(1), Space O(1) class ZigzagIterator(object): def __init__(self, v1, v2): """ Initialize your data structure here. :type v1: List[int] :type v2: List[int] """ self.queue = collections.deque([]) if len(v1) != 0: self.queue.append((0, v1)) if len(v2) != 0: self.queue.append((0, v2)) def next(self): """ :rtype: int """ (i, v) = self.queue.popleft() res = v[i] i += 1 if i != len(v): self.queue.append((i, v)) return res def hasNext(self): """ :rtype: bool """ return len(self.queue) != 0 # Your ZigzagIterator object will be instantiated and called as such: # i, v = ZigzagIterator(v1, v2), [] # while i.hasNext(): v.append(i.next()) Solution: Use list ## https://code.dennyzhang.com/zigzag-iterator ## Basic Ideas: array ## ## Complexity: Time O(1), Space O(1) class ZigzagIterator(object): def __init__(self, v1, v2): """ Initialize your data structure here. :type v1: List[int] :type v2: List[int] """ self.l = [v1, v2] self.indices = [0, 0] self.pos = 0 def next(self): """ :rtype: int """ # skip finished list if self.indices[self.pos] == len(self.l[self.pos]): self.pos = (self.pos + 1)%len(self.l) index = self.indices[self.pos] res = self.l[self.pos][index] self.indices[self.pos] += 1 # flip pointer self.pos = (self.pos + 1)%len(self.l) # TODO: how to avoid the overhead of finished list return res def hasNext(self): """ :rtype: bool """ for i in range(len(self.l)): if self.indices[i] != len(self.l[i]): return True return False # Your ZigzagIterator object will be instantiated and called as such: # i, v = ZigzagIterator(v1, v2), [] # while i.hasNext(): v.append(i.next()) Post Views: 0 Post navigation LeetCode: Lexicographically Smallest Equivalent StringLeetCode: Sentence Screen Fitting Leave a Reply Cancel replyYour email address will not be published.Comment Name Email Website