Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

281. Zigzag Iterator

Time: Constructor: $O(1)$, next(): $O(1)$, hasNext(): $O(1)$

Space: $O(n)$

			


class ZigzagIterator {
 public:
  ZigzagIterator(vector<int>& v1, vector<int>& v2) {
    if (!v1.empty())
      q.emplace(begin(v1), end(v1));
    if (!v2.empty())
      q.emplace(begin(v2), end(v2));
  }

  int next() {
    const auto [it, endIt] = q.front();
    q.pop();
    if (it + 1 != endIt)
      q.emplace(it + 1, endIt);
    return *it;
  }

  bool hasNext() {
    return !q.empty();
  }

 private:
  // {{ it, endIt }}
  queue<pair<vector<int>::iterator, vector<int>::iterator>> q;
};




			


public class ZigzagIterator {
  public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
    if (!v1.isEmpty())
      q.offer(v1.iterator());
    if (!v2.isEmpty())
      q.offer(v2.iterator());
  }

  public int next() {
    final Iterator it = q.poll();
    final int next = (int) it.next();
    if (it.hasNext())
      q.offer(it);
    return next;
  }

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

  private Queue<Iterator> q = new ArrayDeque<>();
}




			


class ZigzagIterator:
  def __init__(self, v1: List[int], v2: List[int]):
    def vals():
      for i in itertools.count():
        for v in v1, v2:
          if i < len(v):
            yield v[i]
    self.vals = vals()
    self.n = len(v1) + len(v2)

  def next(self):
    self.n -= 1
    return next(self.vals)

  def hasNext(self):
    return self.n > 0