Simple iterative DFS using stack


  • 7
    public class NestedIterator implements Iterator<Integer> {
        Stack<Iterator<NestedInteger>> stack = new Stack<>();
        Integer current = null;
        
        public NestedIterator(List<NestedInteger> nestedList) {
            if (nestedList != null) {
                stack.push(nestedList.iterator());
            }
        }
    
        @Override
        public Integer next() {
            return current;
        }
    
        @Override
        public boolean hasNext() {
            while (!stack.isEmpty()) {
                Iterator<NestedInteger> node = stack.peek();
        
                // This will clear out empty iterators.
                if (!node.hasNext()) {
                    stack.pop();
                    continue;
                }
                
                // If the value is an integer, done - load up and return.
                // Otherwise push the current list to the top of the stack and continue.
                NestedInteger value = node.next();
                if (value.isInteger()) {
                    current = value.getInteger();
                    return true;
                } else {
                    stack.push(value.getList().iterator());
                }
            }
            
            return false;
        }
    }

  • 0

    hasNext should be idempotent and optional (so it can be called several times before each next or not at all, and next should still work properly).


  • 1

    Thanks. I think this update should work?

    public class NestedIterator implements Iterator<Integer> {
        Stack<Iterator<NestedInteger>> stack = new Stack<>();
        Integer current = null;
        
        public NestedIterator(List<NestedInteger> nestedList) {
            if (nestedList != null) {
                stack.push(nestedList.iterator());
            }
        }
    
        @Override
        public Integer next() {
            hasNext();
            
            Integer value = current;
            current = null;
            return value;
        }
    
        @Override
        public boolean hasNext() {
            while (current == null && !stack.isEmpty()) {
                Iterator<NestedInteger> node = stack.peek();
                if (!node.hasNext()) {
                    stack.pop();
                    continue;
                }
                
                NestedInteger value = node.next();
                if (value.isInteger()) {
                    current = value.getInteger();
                    return true;
                } else {
                    stack.push(value.getList().iterator());
                }
            }
            
            return false;
        }
    }

  • -1
    T
          List<Object> l;
      Stack<Iterator<Object>> s = new Stack<Iterator<Object>>();
      
      public FlattenList(List<Object> ll) {
        l = ll;
        s.push(l.iterator());
      }
      
    
      public Integer next() {
        Iterator<Object> itr = s.peek();
        Object o = itr.next();
        
        if (o instanceof Integer) {
          return (Integer)o;
        } else {
          while (!(o instanceof Integer)) {
            List<Object> l = (List<Object>) o;
            itr = l.iterator();
            s.push(itr);
            o = itr.next();
          }
          
          return (Integer)o;
        }  
      }
    
      public boolean hasNext() {
        while(true) {
          if (!s.isEmpty()) {
            Iterator<Object> itr = s.peek();
            if (itr.hasNext()) {
              return true;
            } else {
              s.pop();             
            }
          } else {
            return false;
          }
        }
      }
    
      
    }

  • 0
    E

    Same idea, but a slight different way to explain.

    The invariance of the algorithm is to keep the top element of the stack an integer instead of a List. So, for next() operation, we only need to return the top element of the stack and for hasNext(), we only need to return whether the stack is empty or not.

    To enforce the invariant of the algorithm we need to add another operation helper(). After each each next() operation and the initialization, if the invariance got broken, we need to flatten the top list to reinforce the invariance.

    public class NestedIterator implements Iterator<Integer> {

    Deque<NestedInteger> stack = new ArrayDeque<NestedInteger>();
    public NestedIterator(List<NestedInteger> nestedList) {
        Collections.reverse(nestedList);
        for(NestedInteger e: nestedList){
            stack.push(e);
        }
        helper();
    }
    
    @Override
    public Integer next() {
        NestedInteger temp = stack.pop();
        helper();
        return temp.getInteger();
    }
    
    private void helper(){
        while(!stack.isEmpty() && !stack.peek().isInteger()){
            List<NestedInteger> nestedList = stack.pop().getList();
            Collections.reverse(nestedList);
            for(NestedInteger e : nestedList){
                stack.push(e);
            }
        }
    }
    
    @Override
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    

    }


  • 0
    L

    I think there is still a small problem. If you call hasNext() several times before calling next(), only the first hasNext() will return true, and all the hasNext() after that will return false. However, nobody would use an iterator like this :)


Log in to reply
 

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