Two Pass, find max depth and calculate weight sum / T : O(N), S : O(1)


  • 0
    J
    public class Solution {
        public int depthSumInverse(List<NestedInteger> nestedList) {
            // Search Max 
            int max = getMaxHeight(nestedList, 1);
            
            // Calculate Weight Sum
            return calculateWeightSum(nestedList, max);
        }
        
        public int calculateWeightSum(List<NestedInteger> nestedList, int depth){
            int sum = 0;
            for(NestedInteger nI : nestedList){
                if(nI.isInteger()){
                    sum += (depth * nI.getInteger());
                }
                else{
                    sum += calculateWeightSum(nI.getList(), depth - 1);
                }
            }
            return sum;
        }
        
        public int getMaxHeight(List<NestedInteger> nestedList, int depth){
            int max = depth;
            for(NestedInteger nI : nestedList){
                if(!nI.isInteger()){
                    int val = getMaxHeight(nI.getList(), depth+1);
                    if(val > max)
                        max = val;
                }
            }
            return max;
        }
    }
    

Log in to reply
 

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