Java recursive solution using stack. O(h) extra memory (where "h" is the "height" of the list)


  • 0
    A

    Hey there!

    The main idea is to keep only a stack of parent level states. Each state holds a list of NestedIntegers and the last iteration index.

    public class NestedIterator implements Iterator<Integer> {
        private final Stack<State> states;
        private List<NestedInteger> currentList;
        private int currentIndex;
    
        public NestedIterator(List<NestedInteger> nestedList) {
            currentList = nestedList;
            currentIndex = -1;
            states = new Stack<>();
        }
    
        @Override
        public Integer next() {
            return currentList.get(++currentIndex).getInteger();
        }
    
        @Override
        public void remove() {
        }
    
        @Override
        public boolean hasNext() {
            if (moveNext(currentList, currentIndex)) {
                return true;
            }
    
            if (states.size() > 0) {
                State state = states.pop();
                currentList = state.list;
                currentIndex = state.index;
                return hasNext();
            }
    
            return false;
        }
    
        private boolean moveNext(List<NestedInteger> currentList, int currentIndex) {
            for (int i = currentIndex + 1; i < currentList.size(); ++i) {
                NestedInteger nestedInteger = currentList.get(i);
                if (nestedInteger.isInteger()) {
                    this.currentList = currentList;
                    this.currentIndex = i - 1;
                    return true;
                }
    
                List<NestedInteger> list = nestedInteger.getList();
                if (list.isEmpty()) {
                    continue;
                }
    
                states.push(new State(currentList, i));
                if (moveNext(list, -1)) {
                    return true;
                }
                states.pop();
            }
    
            return false;
        }
    
        private static class State {
            private final List<NestedInteger> list;
            private final int index;
    
            public State(List<NestedInteger> list, int index) {
                this.list = list;
                this.index = index;
            }
        }
    }
    

Log in to reply
 

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