Question

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

 281	Zigzag Iterator

 Given two 1d vectors, implement an iterator to return their elements alternately.

 For example, given two 1d vectors:
     v1 = [1, 2]
     v2 = [3, 4, 5, 6]
 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 - Update (2015-09-18):
 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, given the following input:
     [1,2,3]
     [4,5,6,7]
     [8,9]
 It should return
    [1,4,8,2,5,9,3,6,7].

 @tag-design

Algorithm

Extra space to save

Directly when 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

Java

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

All Problems

All Solutions