Zigzag Iterator

Given two vectors of integers v1 and v2, implement an iterator to return their elements alternately.

Given two vectors of integers v1 and v2, implement an iterator to return their elements alternately. Implement the ZigzagIterator class:

• ZigzagIterator(List v1, List 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.

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

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

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

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

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

Approach 1: Two-Pointers

We are asked to iterate the elements while alternating the vectors. One can imagine this as iterating over a two-dimensional matrix, where each row represents an input vector. The idea is that we can employ two pointers for iteration: one pointed to the vector (denoted as p_vec), and the other pointed to the element within the vector (denoted as p_elem). The vector pointer (p_vec) will move in a zigzag (more precisely cyclic) way, i.e., once it reaches the last vector, it will start over from the first vector. The element pointer (p_elem) increments only when the vector pointer finishes a cycle. We give priority to the vector pointer, i.e., we move the vector pointer first, then the element pointer. Algorithm With the above-mentioned two pointers, one should have all the elements needed to implement the function of next(). To implement the function of hasNext(), we can keep account of the number of elements we output so far. Once it reaches the total number of elements in the input, we would know that there is no more element to output. Here are some sample implementations based on the above ideas.

// Define a public class named ZigzagIterator
public class ZigzagIterator {
      // Declare a list of lists to hold the vectors (i.e., 2D list)
      private List> vectors = new ArrayList<>();

      // Pointers to keep track of the current vector and the current element within that vector
      private Integer pVec = 0, pElem = 0;
      
      // Variables to store the total number of elements and the count of elements returned so far
      private Integer totalNum = 0, outputCount = 0;

      // Constructor for ZigzagIterator, takes two lists as input
      public ZigzagIterator(List v1, List v2) {
         // Add the input lists to the vectors list
         this.vectors.add(v1);
         this.vectors.add(v2);
         
         // Calculate the total number of elements in all vectors
         for (List vec : this.vectors) {
            this.totalNum += vec.size();
         }
      }

      // Method to return the next element in zigzag order
      public int next() {
         Integer iterNum = 0, ret = null;
         
         // Iterate over the vectors
         while (iterNum < this.vectors.size()) {
            // Get the current vector
            List currVec = this.vectors.get(this.pVec);
            
            // Check if the current element pointer is within the bounds of the current vector
            if (this.pElem < currVec.size()) {
                  // Get the current element and increase the output count
                  ret = currVec.get(this.pElem);
                  this.outputCount += 1;
            }

            iterNum += 1;
            // Move to the next vector
            this.pVec = (this.pVec + 1) % this.vectors.size();
            
            // If we have iterated through all vectors, move to the next element
            if (this.pVec == 0) {
                  this.pElem += 1;
            }
            
            // If we found a valid element, return it
            if (ret != null) {
                  return ret;
            }
         }

         // If no more elements are found, return 0 (should ideally throw an exception)
         return 0;
      }

      // Method to check if there are more elements to return
      public boolean hasNext() {
         // Return true if the output count is less than the total number of elements
         return this.outputCount < this.totalNum;
      }
}

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

Complexity Analysis

Let K be the number of input vectors, although it is always two in the setting of the problem. This variable becomes relevant, once the input becomes K vectors. Time Complexity: For the next() function, at most it will take us K iterations to find a valid element output. Hence, its time complexity is O(K). For the hasNext() function, its time complexity is O(1). Space Complexity: For the next() function, we keep the references to all the input vectors in the variable self.vectors. As a result, we would need O(K) space for K vectors. In addition, we used some constant-space variables such as the pointers to the vector and the element. Hence, the overall space complexity for this function is O(K). Note: we did not copy the input vectors, but simply keep references to them.