Java Solution: O(1) space without iterators or additional data structures.


  • 1

    I recently had a technical interview where I had to design an iterator class (similar to this problem), and the interviewer did not allow me to use built-in iterators in my solution. So, be careful practicing these questions by using iterators because they do a lot of the work for you and may not be allowed during interviews.

    Here is my solution without built-in iterators or other additional data structures.

    public class ZigzagIterator {
        private int currInt;
        private boolean isv2;
        private List<Integer> v1;
        private List<Integer> v2;
    
        public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
            this.currInt = 0;
            this.v1 = v1;
            this.v2 = v2;
        }
    
        public int next() {
            int out;
            if(!isv2 && currInt < v1.size()) {
                out = v1.get(currInt);
                if(currInt < v2.size())
                    isv2 = true;
                else
                    ++currInt;
            }
            else {
                out = v2.get(currInt++);
                if(currInt < v1.size())
                    isv2 = false;
            }
            return out;
        }
    
        public boolean hasNext() {
            return currInt < v1.size() || currInt < v2.size();
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.