Solution: Nested List Weight Sum II
Let's solve the Nested List Weight Sum II problem using the Tree Depth-First Search pattern.
We'll cover the following
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:
nestedList.length
The values of the integers in the nested list are in the range
maxDepth
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
If it is, we multiply its value by its weight and add the answer to the
result
, where the weight is calculated asmaxDepth - 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:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.