Nested LIst Weight Sum I and II

XXX. Nested List Weight Sum

Recursion

Depth-First Search

Problem Statement:

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Additionally, return the sum of all integers weighted by their inverse depth, where the leaf level has a weight of 1, and the root level has the largest weight.

Algorithm:

1. To calculate the weighted depth sum:
   • Traverse the nested list using DFS.
   • If the element is an integer, add it to the sum multiplied by its depth.
   • If the element is a list, recursively calculate its contribution with increased depth.
2. To calculate the inverse depth sum:
   • First, calculate the maximum depth of the nested list.
   • Traverse the nested list using DFS, but subtract the current depth from the maximum depth to determine the weight.
   • Add each integer multiplied by its inverse depth weight to the sum.

Complexity:

Time Complexity: O(n), where n is the total number of integers and lists.
Space Complexity: O(d), where d is the maximum depth of the nested list (due to recursion stack).

Java Implementation:

public class Solution {
    // Weighted depth sum using DFS
    public int depthSum(List nestedList) {
        return dfs(nestedList, 1);
    }

    public int dfs(List list, int depth) {
        int sum = 0;
        for (NestedInteger nest : list)
            if (nest.isInteger()) 
                sum += nest.getInteger() * depth;
            else 
                sum += dfs(nest.getList(), depth + 1);
        return sum;
    }

    // Weighted inverse depth sum using DFS
    public int depthSumInverse(List nestedList) {
        if (nestedList == null || nestedList.size() == 0) return 0;
        int height = height(nestedList); // Calculate the maximum depth
        return dfs(nestedList, height);
    }

    public int dfs(List nestedList, int level) {
        int sum = 0;
        for (NestedInteger n : nestedList) {
            if (n.isInteger()) sum += level * n.getInteger();
            else sum += dfs(n.getList(), level - 1);
        }
        return sum;
    }

    private int height(List l) {
        if (l.size() == 0) return 0;
        int max = 0;
        for (NestedInteger n : l) {
            if (n.isInteger()) max = Math.max(max, 1);
            else max = Math.max(max, height(n.getList()) + 1);
        }
        return max;
    }
}
                

Python Implementation:

def depth_sum(nested_list):
    def dfs(lst, depth):
        total = 0
        for item in lst:
            if item.isInteger():
                total += item.getInteger() * depth
            else:
                total += dfs(item.getList(), depth + 1)
        return total
    return dfs(nested_list, 1)

def depth_sum_inverse(nested_list):
    def get_height(lst):
        max_depth = 0
        for item in lst:
            if item.isInteger():
                max_depth = max(max_depth, 1)
            else:
                max_depth = max(max_depth, get_height(item.getList()) + 1)
        return max_depth

    def dfs(lst, level):
        total = 0
        for item in lst:
            if item.isInteger():
                total += item.getInteger() * level
            else:
                total += dfs(item.getList(), level - 1)
        return total

    max_depth = get_height(nested_list)
    return dfs(nested_list, max_depth)
                

C++ Implementation:

#include 
#include 
using namespace std;

class NestedInteger {
    // Assume NestedInteger class is implemented
};

int depthSum(vector& nestedList) {
    function&, int)> dfs = [&](vector& list, int depth) {
        int sum = 0;
        for (auto& nest : list)
            if (nest.isInteger())
                sum += nest.getInteger() * depth;
            else
                sum += dfs(nest.getList(), depth + 1);
        return sum;
    };
    return dfs(nestedList, 1);
}

int depthSumInverse(vector& nestedList) {
    function&)> getHeight = [&](vector& l) {
        int maxDepth = 0;
        for (auto& n : l)
            if (n.isInteger())
                maxDepth = max(maxDepth, 1);
            else
                maxDepth = max(maxDepth, getHeight(n.getList()) + 1);
        return maxDepth;
    };

    function&, int)> dfs = [&](vector& list, int level) {
        int sum = 0;
        for (auto& n : list)
            if (n.isInteger())
                sum += n.getInteger() * level;
            else
                sum += dfs(n.getList(), level - 1);
        return sum;
    };

    int height = getHeight(nestedList);
    return dfs(nestedList, height);
}