Java, O(1) space using Iterator with detailed explanation


  • 0

    The idea is to keep two iterators, it1 is a Iterator<List<Integer>> to iterate through the List of Lists. it2 is a Iterator<Integer> which is the the iterator of the List that it1 currently visiting. Whenever we call hasNext we try to find the next appropriate it2. If the current it2 hasNext then we keep using the same it2, otherwise we go down the List of Lists via it1 till we find a List that hasNext. If we reach the end (!it1.hasNext) that means we've exhausted all the possibilities and we return false. next() simply returns it2.next() since hasNext() guarantees that it2 hasNext.

    public class Vector2D implements Iterator<Integer> {
        private Iterator<List<Integer>> it1;
        private Iterator<Integer> it2;
        public Vector2D(List<List<Integer>> vec2d) {
            it1 = vec2d == null ? null : vec2d.iterator();
            it2 = it1 != null && it1.hasNext() ? it1.next().iterator() : null;
        }
    
        @Override
        public Integer next() {
            return it2.next();
        }
    
        @Override
        public boolean hasNext() {  //move it2 to the next available position if needed, if cannot return false;
            if (it2 == null) return false;  //vec2d == null || vec2d.size() == 0
            if (it2.hasNext()) return true; //doesn't need to move it2
            while (it1.hasNext()) {
                it2 = it1.next().iterator();
                if (it2.hasNext()) return true; //find next applicable position for it2
            }
            return false;
        }
    }
    

Log in to reply
 

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