Question

Formatted question description: https://leetcode.ca/all/281.html

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.
boolean hasNext() returns true if the iterator still has elements, and false otherwise.
int next() returns the current element of the iterator and moves the iterator to the next element.

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]

Example 3:

Input: v1 = [], v2 = [1]
Output: [1]

Constraints:

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

Follow up: What if you are given k 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".

Follow-up Example:

Input: v1 = [1,2,3], v2 = [4,5,6,7], v3 = [8,9]
Output: [1,4,8,2,5,9,3,6,7]

Algorithm

Extra space to save

For class initialization, the two arrays are stored in another one-bit array in the order of zigzag, then the values in the new array are printed in order.

need extra space

No extra space

Use two variables i and j to record the current element positions of the two vectors, and initialize them to 0.

Then when i<=j, it means that you need to print the elements of v1 array, otherwise, print the elements of v2 array.

In the hasNext() function, when i or j is printed equal to the length of the corresponding array, assign it to an extra large value, which does not affect the printing of the value of the other array, only when i and j both exceed the length of the lattice array, return false.

Follow up, K iterators

Queue to hold a pair of iterators/indexes. During initialization, add iterator/index pairs and put them in the queue for every iterator. At initialization, each pair stores the the first and last index of the iterator.

In the next() function, take out a pair at the head of the queue. If the current iterator is not equal to end(), store the pari (iterator and the next index) to the queue, and then return the value at the current index.

In the hasNext() function, you only need to see if the queue is empty.

Code

public class Zigzag_Iterator {

    public static void main(String[] args) {

        List<Integer> v1 = Arrays.asList(1,2);
        List<Integer> v2 = Arrays.asList(3, 4, 5, 6);

        Zigzag_Iterator out = new Zigzag_Iterator();
        ZigzagIterator z = out.new ZigzagIterator(v1, v2);

        while (z.hasNext()) {
            System.out.println(z.next());
        }


        List<Integer> v3 = Arrays.asList(1,2,3);
        List<Integer> v4 = Arrays.asList(4,5,6,7);
        List<Integer> v5 = Arrays.asList(8,9);

        List<List<Integer>> vectors = Arrays.asList(v3, v4, v5);
        ZigzagIteratorK zk = out.new ZigzagIteratorK(vectors);

        while (zk.hasNext()) { // [1,4,8,2,5,9,3,6,7]
            System.out.println(zk.next());
        }
    }

    public class ZigzagIteratorK {

        // int[0] is index of vector of vectors list, int[1] is start of a vector, int[2] is end
        Queue<int[]> q = new LinkedList<>();

//        Map<Integer, List<Integer>> vectorsIndexMap = new HashMap<>(); // no map needed, if move 'vectors' a class variable
        List<List<Integer>> vectors;

        public ZigzagIteratorK(List<List<Integer>> vectors) {
            this.vectors = vectors;
            for (int i = 0; i < vectors.size(); i++) {
                q.offer(new int[]{i, 0, vectors.get(i).size()});
//                vectorsIndexMap.put(i, vectors.get(i));
            }
        }

        public int next() {
            int[] current = q.poll();

            int i = current[0];
            int start = current[1];
            int end = current[2];

            if (start + 1 < end) {
                q.offer(new int[]{i, start + 1, end});
            }

//            return vectorsIndexMap.get(i).get(start);
            return vectors.get(i).get(start);
        }

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

    // ZigzagIterator K个也适用
    public class ZigzagIterator_builtinIterator {
        List<Iterator<Integer>> iters = new ArrayList<Iterator<Integer> >();

        int count = 0;

        public ZigzagIterator_builtinIterator(List<Integer> v1, List<Integer> v2) {
            if( !v1.isEmpty() ) {
                iters.add(v1.iterator());
            }
            if( !v2.isEmpty() ) {
                iters.add(v2.iterator());
            }
        }

        public int next() {
            int x = iters.get(count).next();
            if(!iters.get(count).hasNext()) { // remove iterator from list
                iters.remove(count);
            } else {
                count++;
            }

            if(iters.size() != 0) {
                count %= iters.size(); // mod to decide which iterator to get value
            }
            return x;
        }

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

    public class ZigzagIterator {

        List<Integer> result = new ArrayList<>(); // this is extra o(N) space solution, can just maintain a boolean variable
        int index = 0;

        public ZigzagIterator(List<Integer> v1, List<Integer> v2) {

            for (int i = 0; i < Math.max(v1.size(), v2.size()); i++) {
                if (i < v1.size()) {
                    result.add(v1.get(i));
                }
                if (i < v2.size()) {
                    result.add(v2.get(i));
                }
            }
        }

        public int next() {
            return result.get(index++);
        }

        public boolean hasNext() {
            return index < result.size();
        }
    }
}

############

public class ZigzagIterator {
    private int cur;
    private int size;
    private List<Integer> indexes = new ArrayList<>();
    private List<List<Integer>> vectors = new ArrayList<>();

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        cur = 0;
        size = 2;
        indexes.add(0);
        indexes.add(0);
        vectors.add(v1);
        vectors.add(v2);
    }

    public int next() {
        List<Integer> vector = vectors.get(cur);
        int index = indexes.get(cur);
        int res = vector.get(index);
        indexes.set(cur, index + 1);
        cur = (cur + 1) % size;
        return res;
    }

    public boolean hasNext() {
        int start = cur;
        while (indexes.get(cur) == vectors.get(cur).size()) {
            cur = (cur + 1) % size;
            if (start == cur) {
                return false;
            }
        }
        return true;
    }
}

/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator i = new ZigzagIterator(v1, v2);
 * while (i.hasNext()) v[f()] = i.next();
 */

// OJ: https://leetcode.com/problems/zigzag-iterator/
// Time:
//   ZigzagIterator: O(K)
//   next: O(1)
//   hasNext: O(1)
// Space: O(K) where K is the number of input vectors
class ZigzagIterator {
private:
    queue<pair<vector<int>::iterator, vector<int>::iterator>> q;
public:
    ZigzagIterator(vector<int>& v1, vector<int>& v2) {
        if (v1.begin() != v1.end()) q.push(make_pair(v1.begin(), v1.end()));
        if (v2.begin() != v2.end()) q.push(make_pair(v2.begin(), v2.end()));
    }
    int next() {
        auto p = q.front();
        q.pop();
        int val = *p.first;
        p.first++;
        if (p.first != p.second) q.push(p);
        return val;
    }
    bool hasNext() {
        return q.size();
    }
};

class ZigzagIteratorK:

    # int[0] is index of vector of vectors list, int[1] is start of a vector, int[2] is end
    q = []

    # no map needed, if move 'vectors' a class variable
    vectors = []

    def __init__(self, vectors):
        self.vectors = vectors
        for i in range(len(vectors)):
            self.q.append([i, 0, len(vectors[i])])

    def next(self):
        current = self.q.pop(0)

        i = current[0]
        start = current[1]
        end = current[2]

        if start + 1 < end:
            self.q.append([i, start + 1, end])

        return self.vectors[i][start]

    def hasNext(self):
        return len(self.q) != 0

############

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())

############

'''
iter() - builtin function, return an iterator object
    https://docs.python.org/3/library/functions.html#iter


    >>> a = map(iter, [[1,2],[3,4]])
    >>>
    >>> b = next(a)
    >>> b
    <list_iterator object at 0x101630280>
    >>> next(b)
    1
    >>> next(b)
    2
    >>> next(b)
    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    StopIteration


    >>> b = deque(map(iter, [[1,2],[3,4]]))
    >>>
    >>> c = b.popleft()
    >>> c
    <list_iterator object at 0x1016304f0>
    >>> c.next()
    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    AttributeError: 'list_iterator' object has no attribute 'next'
    >>> next(c)
    1
    >>> next(c)
    2
    >>> next(c)
    Traceback (most recent call last):
    File "<stdin>", line 1, in <module>
    StopIteration

len(s) - Return the length (the number of items) of an object
    https://docs.python.org/3/library/functions.html#len
'''

from collections import deque

class ZigzagIterator(object):

  def __init__(self, v1, v2):
    """
    Initialize your data structure here.
    :type v1: List[int]
    :type v2: List[int]
    """
    self.iters = deque(map(iter, [v1, v2]))
    self.total = sum(map(len, [v1, v2]))

  def next(self):
    """
    :rtype: int
    """
    top = self.iters.popleft()
    try:
      value = top.next()
    except StopIteration:
      return self.next()
    self.total -= 1
    if self.total != 0:
      self.iters.append(top)
    return value

  def hasNext(self):
    """
    :rtype: bool
    """
    return self.total > 0

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

struct ZigzagIterator {
    v1: Vec<i32>,
    v2: Vec<i32>,
    /// `false` represents `v1`, `true` represents `v2`
    flag: bool,
}

impl ZigzagIterator {
    fn new(v1: Vec<i32>, v2: Vec<i32>) -> Self {
        Self {
            v1,
            v2,
            // Initially beginning with `v1`
            flag: false,
        }
    }

    fn next(&mut self) -> i32 {
        if !self.flag {
            // v1
            if self.v1.is_empty() && !self.v2.is_empty() {
                self.flag = true;
                let ret = self.v2.remove(0);
                return ret;
            }
            if self.v2.is_empty() {
                let ret = self.v1.remove(0);
                return ret;
            }
            let ret = self.v1.remove(0);
            self.flag = true;
            return ret;
        }  else {
            // v2
            if self.v2.is_empty() && !self.v1.is_empty() {
                self.flag = false;
                let ret = self.v1.remove(0);
                return ret;
            }
            if self.v1.is_empty() {
                let ret = self.v2.remove(0);
                return ret;
            }
            let ret = self.v2.remove(0);
            self.flag = false;
            return ret;
        }
    }

    fn has_next(&self) -> bool {
        !self.v1.is_empty() || !self.v2.is_empty()
    }
}

281 - Zigzag Iterator

Question

Algorithm

Extra space to save

No extra space

Follow up, K iterators

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Extra space to save

No extra space

Follow up, K iterators

Code

All Problems

All Solutions