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. Once the maximum depth is known, the next step is to traverse the nested list again and calculate the sum of each element, weighted by its depth. The weight is derived by subtracting the current depth from the maximum depth and adding one. This ensures that elements at deeper levels have a lower weight, reflecting their reduced contribution to the overall sum. By accumulating these weighted values, the algorithm effectively computes the total weighted sum of the nested list structure.

To calculate the sum of each integer in nested_list multiplied by its weight, 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: