0ms One Pass C++ DFS solution using the idea of Nested List Weight Sum I

  • 2

    In Nested List Weight Sum I we can easily calculate the weighted sum when depth increasing as we see a nested list.
    Here we can use the same idea to calculate the reverse sum by using the weighted sum.
    Suppose we have a nested list, for example, [a, [b], [[c]]]. Then we have the value of weighted sum and reverse weighted sum to be -
    weightedSum = 1a + 2b + 3c
    reverseSum = 3
    a + 2b + 1c
    adding two equations we get
    totalSum = 4*(a+b+c).
    By using above example we can easily conclude that
    reverseSum = (maxDepth+1)* (a+b+c) - weightedSum.
    Then we can use similar DFS solution as used in Nested List Weight Sum I to solve this problem.

        // flatSum = a + b + c -> total sum could be (maxDepth+1)*flatSum
        void getReverseSum(NestedInteger& item, int& maxDepth, int currDepth, int& flatSum, int& weightedSum)
            maxDepth = max(maxDepth, currDepth);
                weightedSum += currDepth*item.getInteger();
                flatSum += item.getInteger();
                vector<NestedInteger>& list = item.getList();
                for(auto& subitem : list)
                    getReverseSum(subitem, maxDepth, currDepth+1, flatSum, weightedSum);
        int depthSumInverse(vector<NestedInteger>& nestedList) 
            int flatSum = 0, weightedSum = 0, maxDepth = 1;
            for(auto& item : nestedList)
                getReverseSum(item, maxDepth, 1, flatSum, weightedSum);
            return flatSum*(maxDepth+1) - weightedSum;

Log in to reply

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