HashMap Java solution with Explanation


  • 9
    H

    HashMap solution

    We have to find the maxDepth before we can do the sum calculation. So we use a HashMap to record the
    integer we visited so far.

    After we visited all inputs and got the maxDepth, we can start to calculate the sum.
    In the HashMap we don't need to record all integers we visited, we just need to record the sum of integers
    in current depth

    Time complexity: O(N), N is num of inputs we have
    Space complexity: O(H), H is maxDepth

     int maxDepth = 0;
    
     public int depthSumInverse(List<NestedInteger> nestedList) {
        //HashMap solution. We use HashMap to store nums in each depth before we find the maxDepth
        //we will do the sum calculation in the last
        
        HashMap<Integer, Integer> hs = new HashMap<Integer, Integer>();
        
        DFS( nestedList, 1, hs );
        
        int sum = 0;
        
        //get sum 
        for( int i = 1; i <= maxDepth; i++ ){
            //put a checker here in case we dont have integer in one layer
            if( hs.containsKey(i ) ) sum += hs.get(i) * (maxDepth + 1 -i);
        }
        
        return sum;
    }
    
     private void DFS(List<NestedInteger> nestedList, int depth,  HashMap<Integer, Integer> hs ){
        //boundary check
        
        if(nestedList.isEmpty()) return;
        
        //update maxDepth if possible
        maxDepth = Math.max(maxDepth, depth);
        
        for( NestedInteger temp : nestedList ){
            if( temp.isInteger() ){
                //if temp is integer
                if( !hs.containsKey(depth) ){
                    hs.put( depth, temp.getInteger()  );
                }else{
                    hs.put( depth, hs.get(depth) + temp.getInteger()  );
                }
            }else{
                //if temp is list
                DFS(  temp.getList(), depth + 1, hs  );
            }
        }
    }

Log in to reply
 

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