O(1) Java implementation without preprocessing


  • 0
    J

    This is my java implementation where all operations (including the constructor itself) takes O(1). All the other solutions require you to pre-process the List so that every element in the list are accessed at least once and then stored into another structure such as stack. However this is not a desired property for an iterator. Since we may use an iterator only to access a few elements in the collection, making an iterator should not depend on the number of elements in the collection.

    public class NestedIterator implements Iterator<Integer> {
        private final ListIterator<NestedInteger> myIter; // iterator used at this level
        private NestedIterator subIter; // iterator used when current NestedInteger is list
    
        // constructor. note that no preprocessing here!
        public NestedIterator(List<NestedInteger> nestedList) {
            myIter = nestedList.listIterator();
            subIter = null;
        }
    
        @Override
        public Integer next() {
            NestedInteger ni = peekNext();
            if (ni.isInteger()) {
                myIter.next();
                return ni.getInteger();
            }
            else {
               if (subIter == null) {
                   subIter = new NestedIterator(ni.getList());    
               }
               return subIter.next();
            }
        }
    
        @Override
        public boolean hasNext() {
            NestedInteger ni = peekNext();
            if (ni == null) return false;
            else if (ni.isInteger()) return true;
            else {
                if (subIter == null) {
                    subIter = new NestedIterator(ni.getList());    
                }
                if (subIter.hasNext()) {
                    return true;
                }
                else {
                    subIter = null;
                    myIter.next();
                    return this.hasNext();
                }
            }
        }
        
        private NestedInteger peekNext() {
            if (myIter.hasNext()) {
                NestedInteger ni = myIter.next();
                myIter.previous();
                return ni;
            }
            return null;
        }
    }
    

Log in to reply
 

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