6 ms java solution with Stack, O(k) space complexity - k is the maximum depth of nested list


  • 0
    V

    Store the next value in 'val'. If next value is not available, 'val' is null. Using a Deque as a Stack to store the nested iterators. If the next value is a list, push the current iterator to the stack, continue searching. Else if next is Integer, set it to 'val' and break;

    public class NestedIterator implements Iterator<Integer> {
        Integer val = null;
        Iterator<NestedInteger> iter = null;
        Deque<Iterator<NestedInteger>> queue = new ArrayDeque<> ();
        public NestedIterator(List<NestedInteger> nestedList) {
            iter = nestedList.iterator();
            next();
        }
    
        @Override
        public Integer next() {
            Integer tmp = val;
            val = null;
            while (iter.hasNext() || !queue.isEmpty()) {
                if (iter.hasNext()) {
                    NestedInteger next = iter.next();
                    if (next.isInteger()) {
                        val = next.getInteger();
                        break;
                    } else {
                        queue.push(iter);
                        iter = next.getList().iterator();
                    }
                } else 
                    iter = queue.pop();
            }
            return tmp;
        }
    
        @Override
        public boolean hasNext() {
            return val != null;
        }
    }
    

Log in to reply
 

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