Solution: Nested List Weight Sum II

Statement

Given a nested list of integers, nested_list, where each element can either be an integer or a list, which can contain integers or more lists, return the sum of each integer in nested_list multiplied by its weight.

The weight of an integer is calculated as max_depth minus the depth of the integer plus one.

The depth of an integer is defined as the number of nested lists it is contained within. For instance, the value of each integer in the list [1,[2,2],[[3],2],1] is equal to its depth. Let max_depth represent the maximum depth of any integer in the nested_list.

Constraints:

• $1 \le$nested_list.length $\le 50$

• The values of the integers in the nested list are in the range $[-100, 100]$

• max_depth $\leq 50$

Solution

The intuition behind the algorithm is to first determine the maximum depth using a depth-first search. Then, perform another depth-first search to compute the weighted sum, where each integer’s weight is given as max_depth - depth + 1.

To calculate the sum of each integer in nested_list multiplied by its weight, we first need to find the weight of every integer. Consequently, to find the weights, we need to calculate max_depth. This is calculated by going deep into each nested list while incrementing the depth at every level. This is a natural fit for a depth-first search approach where we recursively traverse each nested list while incrementing the depth at every recursive call.

After we have max_depth, it’s time to calculate the sum of each integer multiplied by its weight. To visit every integer contained within the nested lists, we start another depth-first search with parameter depth=0. The recursive function first initializes a variable result with $0$. After that, for each nested object, it checks if it’s an integer.

• If it is, we multiply its value by its weight and add the answer to the result, where the weight is calculated as max_depth - depth + 1.

• If it’s not, we call the recursive function with the nested object and incremented depth, i.e., depth+1.

Let’s look at the following illustration to get a better understanding of the solution: