Nested List Weight Sum Ii - Leetcode Solution

Problem Statement:

Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list -- whose elements may also be integers or other lists.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Example:

Input: [[1,1],2,[1,1]]

Output: 8

Explanation: Four 1's at depth 1, one 2 at depth 2.

Solution:

To solve this problem, we need to calculate the depth of each element in the list and the total sum of elements. We will follow the following steps to solve this problem:

• Define a function to calculate the depth of each element in the list. We will use recursion to calculate the depth of each element in the list. If an element is a list, then the depth of all of its elements will be the current depth + 1, and we will take the maximum depth of all elements in the list. If an element is an integer, then the depth will be 1.
• Calculate the total sum of elements. We will use recursion to calculate the sum of all elements in the list. If an element is a list, then we will recursively calculate the sum of all its elements. If an element is an integer, then we will add the depth of that element times the value of that element to the total sum.
• Return the total sum.

Python Code:

def depth_sum_inverse(nestedList): # Calculate the maximum depth of each element in the list. def depth(elem, level): if elem.isInteger(): return level return max(depth(sub_elem, level + 1) for sub_elem in elem.getList())

# Calculate the total sum of elements.
def depth_sum(elem, level):
    if elem.isInteger():
        return level * elem.getInteger()
    return sum(depth_sum(sub_elem, level - 1) for sub_elem in elem.getList())

# Calculate the depth of each element in the list.
max_depth = max(depth(elem, 1) for elem in nestedList)
# Calculate the total sum of elements.
total_sum = sum(depth_sum(elem, max_depth) for elem in nestedList)
return total_sum

Explanation:

In our code, we first define a function depth(elem, level), which takes an element and the current level and returns the maximum depth of the element. If the element is an integer, then the depth is simply the current level. If the element is a list, then we recursively call the function depth() for each element in the list and take the maximum of all depths.

The second function depth_sum(elem, level) calculates the total sum of elements. If the element is an integer, then the depth sum of this element is the product of the element's value and the depth. If the element is a list, then we recursively call the function depth_sum() for each element in the list with the decreased level and sum the results.

Finally, we calculate the maximum depth of all elements in the list using the depth() function and calculate the total sum of all elements using the depth_sum() function for each element in the list.

1