Nested List Weight Sum II

Problem Statement

Given a nestedList comprised of integers and possibly other sub-lists containing more integers or further nested lists, the task is to compute a weighted sum of all integers present in the structure. The peculiarity of the structured data is that every integer's position can be defined by its depth within the nested hierarchy.

Each integer's depth is determined based on how deeply it is nested within other lists. An integer that is not nested within any sub-list has a depth of 1, while one nested inside one sub-list has a depth of 2, and so forth. The weight of each integer is calculated based on the difference between its depth and the deepest depth, maxDepth, found across all integers, plus one.

Your goal is to return the total sum wherein each integer is multiplied by its respective weight.

Examples

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.
• There are no empty lists.

Approach and Intuition

To solve the problem, the strategy revolves around first determining the maxDepth to correctly calculate the weights, followed by computing the weighted sum.

1. Calculate the maxDepth:

   • Traverse through the nestedList to find the depth of the deepest integer.
   • A recursive function can help in calculating the depth of each integer efficiently.

2. Compute weights and the weighted sum:

   • For each integer, compute the weight using the formula maxDepth - (depth of the integer) + 1.
   • Multiply each integer by its calculated weight and aggregate these values to get the final result.

Given the constraints and the nature of nestedList, the recursive approach will involve checking each element to determine if it's an integer or a list. If it's a list, the function recursively checks its contents. This will efficiently ensure all integers are processed for their respective depths and weights.

The examples show how deeply nested integers contribute differently to the weighted sum based on their position in the structure. For example, an integer closer to the outer list will have a higher weight compared to one that is deeply nested.

By handling lists and integers recursively and keeping track of the current depth, we can accurately apply weights and calculate the total sum expected by the problem statement. This approach covers scenarios for varied depths and compositions of the nestedList.

Solutions

class Solution {
public:
    int inverseDepthSum(vector<NestedInteger>& nestedData) {
        queue<NestedInteger> processQueue;
        for (NestedInteger item : nestedData) {
            processQueue.push(item);
        }
    
        int currentDepth = 1;
        int deepestDepth = 0;
        int totalValues = 0;
        int weightedSum = 0;
    
        while (!processQueue.empty()) {
            int levelSize = processQueue.size();
            deepestDepth = max(deepestDepth, currentDepth);
                
            for (int i = 0; i < levelSize; i++) {
                NestedInteger current = processQueue.front(); 
                processQueue.pop();
                    
                if (current.isInteger()) {
                    totalValues += current.getInteger();
                    weightedSum += current.getInteger() * currentDepth;
                } else {
                    for (NestedInteger nextItem : current.getList()) {
                        processQueue.push(nextItem);
                    }
                }
            }
            currentDepth++;
        }
        return (deepestDepth + 1) * totalValues - weightedSum;
    }
};