Simple Java solution using a stack with explanation


  • 144
    Y

    A question before this is the Nested List Weight Sum, and it requires recursion to solve. As it carries to this problem that we will need recursion to solve it. But since we need to access each NestedInteger at a time, we will use a stack to help.

    In the constructor, we push all the nestedList into the stack from back to front, so when we pop the stack, it returns the very first element. Second, in the hasNext() function, we peek the first element in stack currently, and if it is an Integer, we will return true and pop the element. If it is a list, we will further flatten it. This is iterative version of flatting the nested list. Again, we need to iterate from the back to front of the list.

    public class NestedIterator implements Iterator<Integer> {
        Stack<NestedInteger> stack = new Stack<>();
        public NestedIterator(List<NestedInteger> nestedList) {
            for(int i = nestedList.size() - 1; i >= 0; i--) {
                stack.push(nestedList.get(i));
            }
        }
    
        @Override
        public Integer next() {
            return stack.pop().getInteger();
        }
    
        @Override
        public boolean hasNext() {
            while(!stack.isEmpty()) {
                NestedInteger curr = stack.peek();
                if(curr.isInteger()) {
                    return true;
                }
                stack.pop();
                for(int i = curr.getList().size() - 1; i >= 0; i--) {
                    stack.push(curr.getList().get(i));
                }
            }
            return false;
        }
    }

  • 18
    L

    Same idea. But I guess the code could be conciser.

    public class NestedIterator implements Iterator<Integer> {
        Deque<NestedInteger> s;
    
        public NestedIterator(List<NestedInteger> nestedList) {
            s = new ArrayDeque<>(nestedList == null ? Arrays.asList() : nestedList);
        }
        
        @Override
        public Integer next() {
            return s.pollFirst().getInteger();
        }
    
        @Override
        public boolean hasNext() {
            while(!s.isEmpty() && !s.peekFirst().isInteger()) {
                List<NestedInteger> list = s.pollFirst().getList();
                for (int i=list.size()-1; i>=0; i--) s.addFirst(list.get(i));
            }
            return !s.isEmpty();
        }
    }

  • 0
    A

    best solution ever!


  • 0

    Just curious what is the running time of this solution? It looks like the stack will contain maximum of (depth * average child nodes) elements, while the traditional dfs's backtrack stack contains maximum of depth elements.


  • 24
    A

    like your clean code.
    a small comment is that your solution works only if we always call hasNext() before calling next(). certainly meet requirement of this problem but not generic for iterator. a small modification can make it more generic, if needed.


  • 0
    C

    Thanks. C++ version of the same solution:

    class NestedIterator {
    public:
        stack<NestedInteger> stk;
        NestedIterator(vector<NestedInteger> &nestedList) {
            for (int i = nestedList.size() - 1; i >= 0; i--)
                stk.push(nestedList[i]);
        }       
    
        int next() {
            int val = stk.top().getInteger();
            stk.pop(); 
            return val;
        }       
    
        bool hasNext() {
            while (!stk.empty()) {
                NestedInteger curr = stk.top();
                if (curr.isInteger()) return true;
                stk.pop();
                for (int i = curr.getList().size() - 1; i >= 0; i--)
                    stk.push((curr.getList())[i]);
            }           
            return false;
        }       
    };

  • 37
    F

    Guess what @AlexTheGreat means is to call hasNext() before next() internally to avoid exception, like below:

    public class NestedIterator implements Iterator<Integer> {
    
        private Stack<NestedInteger> stack;
    
        public NestedIterator(List<NestedInteger> nestedList) {
            stack = new Stack<>();
            flattenList(nestedList);
        }
    
        @Override
        public Integer next() {
            return hasNext() ? stack.pop().getInteger() : null;
        }
    
        @Override
        public boolean hasNext() {
            while (!stack.isEmpty()) {
                if (stack.peek().isInteger()) return true;
                flattenList(stack.pop().getList());
            }
            return false;
        }
    
        private void flattenList(List<NestedInteger> list) {
            for (int i = list.size() - 1; i >= 0; i--) {
                stack.push(list.get(i));
            }
        }
    }

  • 0
    C

    C# version

    public class NestedIterator {
    
        private Stack<NestedInteger> stack = new Stack<NestedInteger>();
        
        public NestedIterator(IList<NestedInteger> nestedList) {
            for (int i = nestedList.Count() - 1; i >= 0; i--)
            {
                stack.Push(nestedList.ElementAt(i));
            }
        }
    
        public bool HasNext() {
            while (stack.Count != 0)
            {
                NestedInteger cur = stack.Peek();
                if (cur == null) return false;
                if (cur.IsInteger())
                {
                    return true;
                }
    
                stack.Pop();
                for (int i = cur.GetList().Count() - 1; i >= 0; i--)
                {
                    stack.Push(cur.GetList().ElementAt(i));
                }
            }
            return false;            
        }
    
        public int Next() {
            return stack.Pop().GetInteger();    
        }
    }

  • 11
    D

    hasNext shouldn't be changing state. It would be cleaner if hasNext simply returns false if the stack is empty, otherwise true. Then, make next do the work that is currently in hasNext.


  • 0
    Y

    if recursion, then can get the list first.

    '''
    public class NestedIterator implements Iterator<Integer> {
    LinkedList<Integer> q = new LinkedList<Integer>();
    public NestedIterator(List<NestedInteger> nestedList) {
    helper(nestedList);
    }

    @Override
    public Integer next() {
        return q.poll();
    }
    
    @Override
    public boolean hasNext() {
        return q.size() > 0;
    }
    
    public void helper(List<NestedInteger> nl){
        for(NestedInteger val: nl){
            if (val.isInteger()){
                q.add(val.getInteger());
            } else {
                helper(val.getList());     
            }
        }
    }
    

    }
    '''


  • 0
    L
    This post is deleted!

  • 1
    A

    @church1985 I think it's better to use reference in C++ version. Here is my code.

    class NestedIterator {
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            for(int i = nestedList.size() - 1; i >= 0; --i) {
                st.push(&nestedList[i]);
            }
        }
    
        int next() {
            int next = st.top()->getInteger();
            st.pop();
            return next;
        }
    
        bool hasNext() {
            while(!st.empty()) {
                if(st.top()->isInteger())  return true;
                vector<NestedInteger> &list(st.top()->getList());
                st.pop();
                for(int i = list.size() - 1; i >= 0; --i) {
                    st.push(&list[i]);
                }
            }
            
            return false;
        }
        
    private:
        stack<NestedInteger*> st;
    };
    
    

  • 0

    this is the easy way of cheating kind of.
    More fun in designing the actual Iterator class working the way Iterator did, which is process one by one exactly


  • 0
    W

    same idea for javascript.

    /**
     * @constructor
     * @param {NestedInteger[]} nestedList
     */
    var NestedIterator = function(nestedList) {
        var stack = [];
        
        for (var i=nestedList.length-1; i>=0; i--){
            stack.push(nestedList[i]);
        }
        this.stack = stack;
    };
    
    /**
     * @this NestedIterator
     * @returns {boolean}
     */
    NestedIterator.prototype.hasNext = function() {
        var stack = this.stack;
        while(stack.length > 0){
            var node = stack.pop();
            if (node.isInteger()){
                stack.push(node);
                return true;
            }
            var list = node.getList();
            for (var i = list.length-1; i>=0; i--){
                stack.push(list[i]);
            }
        }
    };
    
    /**
     * @this NestedIterator
     * @returns {integer}
     */
    NestedIterator.prototype.next = function() {
        return this.stack.pop().getInteger();
    };
    

  • 0
    G

    Thanks for the great solution. Below is my java solution (10ms) using two HashMaps. One map to maintain nestedList at each level and other two keep track of counter at each level. Its little complex but approach is very logical and space efficient rather in-place.

    public class NestedIterator implements Iterator<Integer> {
        Map<Integer,List<NestedInteger>> listMap;
        Map<Integer,Integer> countMap;
        int level;
        List<NestedInteger> curList;
        int i;
        public NestedIterator(List<NestedInteger> nestedList) {
            listMap = new HashMap<Integer,List<NestedInteger>>();
            countMap = new HashMap<Integer,Integer>();
            level = 0;
            i = 0;
            curList = nestedList;
            listMap.put(level,curList);
            countMap.put(level,i);
        }
    
        @Override
        public Integer next() {
            countMap.put(level,++i);
            return curList.get(i-1).getInteger();
        }
    
        @Override
        public boolean hasNext() {
            curList = listMap.get(level);
            i = countMap.get(level);
            while(i<curList.size() || level > 0){
                while(i==curList.size() && level > 0){
                    listMap.remove(level);
                    countMap.remove(level);
                    level--;
                    curList = listMap.get(level);
                    i = countMap.get(level);
                }
                if(i==curList.size() && level == 0) return false;
                NestedInteger n = curList.get(i);
                if(n.isInteger()){
                    return true;
                }
                curList = n.getList();
                countMap.put(level,++i);
                level++;
                i = 0;
                listMap.put(level,curList);
                countMap.put(level,i);
            }
            return false;
        }
    }
    

  • 2

    @lixx2100 Very concise and crystal clear! I like it!


  • 2

    Thanks for sharing! I used Stack as well but store iterator instead to iterate one by one. Here is mine for reference.

        private Stack<Iterator<NestedInteger>> s = new Stack<>();
        
        private Integer nextInt;
    
        public NestedIterator(List<NestedInteger> nestedList) {
            if (!nestedList.isEmpty()) s.push(nestedList.iterator());
        }
    
        @Override
        public Integer next() {
            Integer ret = nextInt;
            nextInt = null;
            return ret;
        }
    
        @Override
        public boolean hasNext() { // Find next NI that is not a list
            while (!s.isEmpty() && nextInt == null) {
                if (s.peek().hasNext()) {
                    NestedInteger ni = s.peek().next();
                    if (ni.isInteger()) nextInt = ni.getInteger();
                    else s.push(ni.getList().iterator());
                } else s.pop();
            }
            return nextInt != null;
        }
    

  • 3
    C

    why cant we use queue instead of stack here?


  • 0

    @cdai in my opinion this is the best approach, store iterators. I have similar here, but the iterator in C# is pretty ugly so I substituted with my own data pair class.

    The idea is you always seek to the next integer, then your next is that element. Upon construction and after every next, again seek to the next integer. The stack will only need to hold lists that you need to revisit due to diving down a sub list. I see a lot of solutions that push all the elements from the current list onto a stack a head of time. Seems unnecessary.

    public class NestedIterator 
    {
        Stack<Pos> stack = new Stack<Pos>();
        Pos curr = null;
        
        public NestedIterator(IList<NestedInteger> nestedList) 
        {
            curr = NextInteger(new Pos(nestedList, -1)); // little trick starting at -1
        }
    
        public bool HasNext() 
        {
            return curr.index < curr.list.Count;
        }
    
        public int Next() 
        {
            int x = HasNext() ? curr.list[curr.index].GetInteger() : -1;
            curr = NextInteger(curr);
            return x;
        }
        
        private Pos NextInteger(Pos p)
        {
            p.index++;
            
            while (p.index < p.list.Count || stack.Count > 0)
            {
                if (p.index < p.list.Count)
                {
                    if (p.list[p.index].IsInteger()) break;
                    
                    if (p.index + 1 < p.list.Count) 
                        stack.Push(new Pos(p.list, p.index + 1));
                        
                    p = new Pos(p.list[p.index].GetList(), 0);
                }
                else
                {
                    p = stack.Pop();
                }
            }
            
            return p;
        }
    }
    
    // tuple to hold list and index
    public class Pos
    {
        public IList<NestedInteger> list;
        public int index;
        
        public Pos(IList<NestedInteger> list, int index)
        {
            this.list = list;
            this.index = index;
        }
    }
    

  • 1
    I

    @dstephens98177 I had the same thought as you. It's unnatural to change state in hasNext(), it should just return true or false according to whether the stack is empty. But there is a big problem when I implement it in the natural way. For the test case "[]", hasNext() will return true since the stack is not empty(empty nested list is still a nested list), but actually there is no "next integer" in this list. It's impossible for next() to return a valid value since it can only return a int but we need a NULL or something makes cout print nothing. So we should first flatten the list and then check if the stack is really empty, that's the job hasNext() should do.


Log in to reply
 

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