364

364. Nested List Weight Sum II (Medium)

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.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer's value set to its depth. Let maxDepth be the maximum depth of any integer.

The weight of an integer is maxDepth - (the depth of the integer) + 1.

Return the sum of each integer in nestedList multiplied by its weight.

 

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's with a weight of 1, one 2 with a weight of 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: 17
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1.
1*3 + 4*2 + 6*1 = 17

 

Constraints:

• 1 <= nestedList.length <= 50
• The values of the integers in the nested list is in the range [-100, 100].
• The maximum depth of any integer is less than or equal to 50.

Companies:
LinkedIn

Related Topics:
Stack, Depth-First Search, Breadth-First Search

Similar Questions:

• Nested List Weight Sum (Medium)
• Array Nesting (Medium)

Solution 1. Double Pass DFS

// OJ: https://leetcode.com/problems/nested-list-weight-sum-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
private:
    int getDepth(vector<NestedInteger>& nestedList) {
        int ans = 0;
        for (auto &item : nestedList) ans = max(ans, item.isInteger() ? 0 : getDepth(item.getList()));
        return 1 + ans;
    }
    int getSum(vector<NestedInteger>& nestedList, int weight) {
        int sum = 0;
        for (auto &item : nestedList) sum += item.isInteger() ? (item.getInteger() * weight) : getSum(item.getList(), weight - 1);
        return sum;
    }
public:
    int depthSumInverse(vector<NestedInteger>& nestedList) {
        int depth = getDepth(nestedList);
        return getSum(nestedList, depth);
    }
};

Solution 2. Single Pass BFS

Each integer get added one extra time for the mere existence of each one level under it.

// OJ: https://leetcode.com/problems/nested-list-weight-sum-ii/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
private:
public:
    int depthSumInverse(vector<NestedInteger>& list) {
        queue<NestedInteger> q;
        for (auto &item : list) q.push(item);
        int ans = 0, unweighted = 0;
        while (q.size()) {
            int cnt = q.size();
            while (cnt--) {
                auto ni = q.front();
                q.pop();
                if (ni.isInteger()) {
                    unweighted += ni.getInteger();
                } else { 
                    for (auto &item : ni.getList()) q.push(item);
                }
            }
            ans += unweighted;
        }
        return ans;
    }
};