341. Flatten Nested List Iterator

Problem Link: https://leetcode.com/problems/flatten-nested-list-iterator/

Description:

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

• NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
• int next() Returns the next integer in the nested list.
• boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Solution:

Visualize the Nested Iterator as a Disjoin Set, where each Nested Integer is a node. Put all the initial nodes in a queue, and explore each node.

If the node at head of queue is an integer, simply put it back and increment the counter of number of integers in the queue.

Else if it is a List of NestedInteger, put the individual elements of that list into the Queue, and move to next level.

Code:

        for(NestedInteger nI : nestedList){
            
            if(nI.isInteger()){
               
                numIntegers++;
            }
            
            queue.offer(nI);
        }


        
        while(queue.size()!= 0 && numIntegers!= queue.size()){
            
            numIntegers = 0;
           
            int levelSize = queue.size();
            
            for(int i = 0; i<levelSize; i++){
                
                NestedInteger nI = queue.poll();
                
                if(nI.isInteger()){
                   
                    numIntegers++;
                    
                    queue.offer(nI);
                    
                    continue;
                }
                
                List<NestedInteger> list = nI.getList();
                
                for(NestedInteger ni_ : list){
                    
                    queue.offer(ni_);
                
                }
                
            }
            
        }         

Once the queue is ready, the next and hasNext functions can be easily accomplished.

    @Override
    public Integer next() {
        
        if(queue.size()!=0){
            return queue.peek().isInteger() ? queue.poll().getInteger() : null;
        }
        
        return null;
        
    }


    @Override
    public boolean hasNext() {
        
        return queue.size() != 0;
        
    }
}