Show problems as
Classic problem #364MediumStackDepth-First SearchBreadth-First Search

Nested List Weight Sum II

Real-world version: Weighting a Nested Parts File
Tracked in this browser only
Read Nested List Weight Sum II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A parts file arrives as nestedList, a list whose entries are each either a whole number or another list built the same way. No list anywhere in the file is empty.

The level of an entry is how many lists have to be opened to reach it. An entry written directly inside nestedList is at level 1, an entry inside a list that is itself inside nestedList is at level 2, and so on. Write D for the largest level at which a whole number appears anywhere in the file.

The weight of a whole number that sits at level L is D - L + 1. So the whole numbers buried deepest carry weight 1, those one level up carry weight 2, and those written at level 1 carry weight D.

Return the sum, over every whole number in the file, of that number multiplied by its weight.

Examples

Example 1

Input
nestedList = [2, [5, [7]]]
Output
23

The number 2 sits at level 1, 5 at level 2 and 7 at level 3, so D is 3. The weights are then 3, 2 and 1, which gives 6 plus 10 plus 7.

Example 2

Input
nestedList = [7, 3, -2]
Output
8

Every number sits at level 1 and D is 1, so each weight is 1 and the answer is just 7 + 3 - 2 = 8.

Example 3

Input
nestedList = [-100, [100]]
Output
-100

Here D is 2. The number -100 sits at level 1 with weight 2 and 100 sits at level 2 with weight 1, so the answer is -200 + 100 = -100.

Constraints

  • 1 <= nestedList.length <= 50
  • Every whole number in the file lies in the range [-100, 100].
  • No whole number sits at a level greater than 50.
  • No list in the file is empty.
  • The file holds at most 500 whole numbers in total, so the answer stays well inside 10^7 in absolute value.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def depth_sum_inverse(nestedList: list) -> int:
Java
public int depthSumInverse(List<NestedInteger> nestedList)

More on the same topics