Vultr DocsLatest Content

Nested List Weight Sum II

Updated on 18 June, 2025
Nested List Weight Sum II header image

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

  • C++
  • Java
cpp 
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;
    }
};

In the provided C++ solution to the problem "Nested List Weight Sum II," the program calculates the sum of integers in a nested list, weighed by the inverse of their depth levels. This sum is then modified to meet specific conditions tied to the depth calculation. Review the process implemented in the code:

  • A queue<NestedInteger> is employed to traverse through the nested data in a level-by-level manner using Breadth-First Search (BFS).

  • The program initializes several helpers including currentDepth to track the level during traversal and deepestDepth to store the maximum depth encountered. totalValues aggregates the raw integer values present, and weightedSum holds the sum of integers each multiplied by their respective depth.

  • The main loop runs until the queue is empty, processing all items level by level. Each integer's value is added to totalValues, and its value multiplied by currentDepth is added to weightedSum.

  • After traversing all items, the solution computes the final result using the formula (deepestDepth + 1) * totalValues - weightedSum. This formula aims to adjust the weighted sum by reversing the impact of depth on the values.

By the completion of this implementation, the program successfully computes the customized weighted sum for a given nested list, considering the intricate structure and variable depths of nested elements. This method provides a clear mechanics for handling nested data structures with numerical entries, showcasing a practical application of BFS in such contexts.

java 
class Solution {
    public int calcWeightedSum(List<NestedInteger> nestedList) {
        Queue<NestedInteger> queue = new LinkedList<>();
        queue.addAll(nestedList);

        int currentDepth = 1;
        int deepest = 0;
        int totalElementsSum = 0;
        int weightedSum = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            deepest = Math.max(deepest, currentDepth);
            
            for (int i = 0; i < levelSize; i++) {
                NestedInteger item = queue.poll();
                
                if (item.isInteger()) {
                    totalElementsSum += item.getInteger();
                    weightedSum += item.getInteger() * currentDepth;
                } else {
                    queue.addAll(item.getList());
                }
            }
            currentDepth++;
        }
        return (deepest + 1) * totalElementsSum - weightedSum;
    }
}

The Java solution provided focuses on calculating a weighted sum from a nested list where deeper elements contribute less to the final score. Implement a method calcWeightedSum, utilizing a breadth-first search approach with a queue. Follow these steps to understand the implemented logic:

  1. Initialize a queue and add all elements from the nested list input to the queue.
  2. Use variables currentDepth to track the current depth, deepest to record the deepest level, totalElementsSum to store the sum of all integers, and weightedSum for the preliminary weighted sum where deeper integers weigh more.
  3. Process the queue using a while loop until it is empty. For each level:
    • Determine the number of elements (levelSize).
    • Update deepest with the maximum of deepest or currentDepth.
    • Iterate over each element of the current level:
      • If it's an integer, add its value to totalElementsSum and its weighted value (value multiplied by depth) to weightedSum.
      • If it's a list, enqueue its elements for further processing.
    • Increment currentDepth by 1 after processing each level.
  4. Calculate the final weighted sum by adjusting weightedSum using the formula (deepest + 1) * totalElementsSum - weightedSum, effectively reducing the weight of deeper elements.

The method returns the adjusted weightedSum, representing the sum where each integer's contribution is inversely proportional to its depth, making deeper numbers less influential on the final sum outcome.

Comments

No comments yet.