Solution: Nested List Weight Sum II

Statement

Given a nested list of integers, nestedList, 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 nestedList multiplied by its weight.

The weight of an integer is calculated as maxDepth 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 maxDepth represent the maximum depth of any integer in the nestedList.

Constraints:

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

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

• maxDepth $\le 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 maxDepth - depth + 1.

To calculate the sum of each integer in nestedList multiplied by its weight, we first need to find the weight of every integer. Consequently, to find the weights, we need to calculate maxDepth. 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 maxDepth, 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 maxDepth - 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: