Nested List Weight Sum - Leetcode Solution

The Nested List Weight Sum problem on leetcode asks us to find the sum of all integers in a nested list of integers, where each element can be either an integer or a list. The weight of each integer is its depth in the nested list multiplied by its value.

For example, consider the following nested list [[1,1],2,[1,1]], the depth of the integers 1 and 1 is 2 (they are nested within a list nested within another list), and the depth of integer 2 is 1 (it is at the top level). Therefore, the weight of the nested list is (12) + (21) + (12) + (12) = 8.

To solve this problem, we can use recursion. We can define a function nestedListWeightSum that takes in a nested list and the current depth, and recursively calculates the sum. If the element is an integer, we simply add its weight to the total sum. If it is a list, we recursively call the function with the nested list and the current depth + 1.

Here is the detailed solution in Python:

def nestedListWeightSum(nestedList, depth=1):
    totalSum = 0
    for item in nestedList:
        if isinstance(item, int):
            totalSum += item * depth
        elif isinstance(item, list):
            totalSum += nestedListWeightSum(item, depth+1)
    return totalSum

The function takes a nestedList and a depth (which is optional and defaults to 1). We initialize the totalSum to 0 and loop through each item in the nested list.

If the item is an integer, we add its weight to the total sum by multiplying it with the current depth. If the item is a list, we recursively call the function with the nested list and the current depth + 1, and add the result to the total sum.

Finally, we return the total sum.

We can test this function with the example nested list [[1,1],2,[1,1]] as follows:

nestedList = [[1,1],2,[1,1]]
print(nestedListWeightSum(nestedList))

This should output 8 as expected.

This solution has a time complexity of O(n), where n is the total number of integers in the nested list. This is because we need to visit every integer once to calculate its weight. It also has a space complexity of O(d), where d is the maximum depth of the nested list, because we need to store the depth for each recursive call.

1