0605MediumStackDepth-First SearchBreadth-First Search

Weighting a Nested Parts File

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def depth_sum_inverse(nestedList: list) -> int:

Java

public int depthSumInverse(List<NestedInteger> nestedList)

The intended approach

Time O(N), where N is the number of entries in the file, since each entry is looked at once.Space O(W) for the level being built, where W is the widest level.

The weight of a number depends on the deepest level in the whole file, which is not known until the file has been read, so add up the numbers level by level first and apply the weights afterwards. Starting from the top list, sum the whole numbers on the current level and gather the contents of every list on it to form the next level; because no list is empty, the sweep ends exactly one step past the deepest level, so the count of level totals collected is `D`. The total gathered from level `i` then contributes `D - i + 1` times its value.

Pythonentry point: depth_sum_inverse

def depth_sum_inverse(nestedList):
    # O(N) time and O(W) space, where N counts every entry in the file and W is
    # the widest level. Sweep one level at a time, adding up the whole numbers on
    # that level and collecting the entries of every list found there to form the
    # next level. The sweep stops when a level has no entries, so the number of
    # level totals collected is exactly the deepest level D. A total from level i
    # (counting from 1) is then multiplied by D - i + 1.
    per_level = []
    level = nestedList
    while level:
        running = 0
        deeper = []
        for entry in level:
            if isinstance(entry, list):
                for inner in entry:
                    deeper.append(inner)
            else:
                running += entry
        per_level.append(running)
        level = deeper
    deepest = len(per_level)
    total = 0
    for i in range(deepest):
        total += per_level[i] * (deepest - i)
    return total

The obvious version

Walk the file with an explicit stack of (list, level) pairs, recording every whole number together with the level it was found at. Then take the largest level recorded and add up each recorded number times its own weight.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_depth_sum_inverse(nestedList):
    found = []
    stack = [(nestedList, 1)]
    while stack:
        node, level = stack.pop()
        for entry in node:
            if isinstance(entry, list):
                stack.append((entry, level + 1))
            else:
                found.append((entry, level))
    deepest = 0
    for _, level in found:
        if level > deepest:
            deepest = level
    total = 0
    for value, level in found:
        total += value * (deepest - level + 1)
    return total

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in