LeetCode 364: Nested List Weight Sum II

Problem Restatement

We are given a nested list.

Each element is either:

an integer

or:

a list containing integers or more nested lists

We need to return the weighted sum of all integers.

This problem uses inverse depth weights.

That means integers closer to the top have larger weight, and integers at the deepest level have weight 1.

The official statement says this differs from the previous Nested List Weight Sum problem: here the leaf-level integers have weight 1, while root-level integers have the largest weight. For example, [1,[4,[6]]] gives 1 * 3 + 4 * 2 + 6 * 1 = 17.

Input and Output

Example function shape:

def depthSumInverse(nestedList: list[NestedInteger]) -> int:
    ...

LeetCode provides the NestedInteger interface. We should not implement or assume its internals.

It supports these methods:

isInteger()
getInteger()
getList()

Examples

Example 1:

nestedList = [[1, 1], 2, [1, 1]]

The integers are:

So the answer is:

1 + 1 + 2 * 2 + 1 + 1 = 8

Example 2:

nestedList = [1, [4, [6]]]

The deepest integer is 6, so the maximum depth is 3.

Answer:

17

First Thought: Find Max Depth, Then Sum

A direct solution uses two DFS passes.

First pass:

find the maximum depth

Second pass:

sum each integer times maxDepth - depth + 1

This works and is easy to prove.

But there is a cleaner one-pass level-order idea.

Key Insight

Instead of computing the maximum depth directly, process the nested list level by level.

At each level, keep a running sum of all integers seen so far.

Then add that running sum to the answer once per level.

Why does this create inverse depth weights?

Consider:

[1, [4, [6]]]

Process by levels:

Total:

1 + 5 + 11 = 17

The top-level 1 is included at levels 1, 2, and 3, so it is counted 3 times.

The 4 is included at levels 2 and 3, so it is counted 2 times.

The 6 is included only at level 3, so it is counted 1 time.

That exactly matches inverse depth weighting.

Algorithm

Use BFS by levels.

Maintain:

Steps:

1. Set current_level = nestedList.
2. Set unweighted = 0.
3. Set weighted = 0.
4. While current_level is not empty:
   • Create next_level = [].
   • For each item in current_level:
     • If it is an integer, add it to unweighted.
     • Otherwise, append its children to next_level.
   • Add unweighted to weighted.
   • Move to next_level.
5. Return weighted.

Correctness

The BFS loop processes the nested structure one depth level at a time.

When an integer appears at depth d, it is first added to unweighted while processing level d.

After that, unweighted is added to weighted once for every remaining level, including level d.

If the maximum depth is D, then an integer at depth d contributes to weighted exactly:

D - d + 1

times.

That is precisely the inverse depth weight required by the problem.

Every integer is added to unweighted exactly once, when its own level is processed. Lists only pass their children to the next level and do not directly affect the sum.

Therefore, the final weighted value equals the required inverse depth weighted sum.

Complexity

Let N be the total number of NestedInteger objects, including integers and lists.

In the worst case, W can be O(N).

Implementation

class Solution:
    def depthSumInverse(self, nestedList: list["NestedInteger"]) -> int:
        current_level = nestedList

        unweighted = 0
        weighted = 0

        while current_level:
            next_level = []

            for item in current_level:
                if item.isInteger():
                    unweighted += item.getInteger()
                else:
                    next_level.extend(item.getList())

            weighted += unweighted
            current_level = next_level

        return weighted

Code Explanation

We start from the top-level list:

current_level = nestedList

The variable unweighted stores the sum of every integer seen so far:

unweighted = 0

The variable weighted stores the final answer:

weighted = 0

At each level, we prepare the next level:

next_level = []

If an item is an integer, we add it to the running sum:

if item.isInteger():
    unweighted += item.getInteger()

If an item is a list, we move its children to the next level:

else:
    next_level.extend(item.getList())

After finishing the level, we add unweighted to weighted:

weighted += unweighted

This is the key line.

It makes earlier integers count again at deeper levels.

Then we move downward:

current_level = next_level

Alternative Implementation: Two-Pass DFS

We can also solve the problem by first collecting values by depth.

class Solution:
    def depthSumInverse(self, nestedList: list["NestedInteger"]) -> int:
        values = []

        def dfs(items: list["NestedInteger"], depth: int) -> None:
            if depth == len(values):
                values.append(0)

            for item in items:
                if item.isInteger():
                    values[depth] += item.getInteger()
                else:
                    dfs(item.getList(), depth + 1)

        dfs(nestedList, 0)

        answer = 0
        max_depth = len(values)

        for depth, level_sum in enumerate(values):
            weight = max_depth - depth
            answer += level_sum * weight

        return answer

This version is also correct. The BFS running-sum version is shorter and avoids explicitly computing weights.

Testing

Because LeetCode provides NestedInteger, local testing needs a small mock class.

class NestedInteger:
    def __init__(self, value=None):
        self.value = value
        self.children = []

    def isInteger(self):
        return self.value is not None

    def getInteger(self):
        return self.value

    def getList(self):
        return self.children

    def add(self, item):
        self.children.append(item)

def build(data):
    if isinstance(data, int):
        return NestedInteger(data)

    node = NestedInteger()
    for item in data:
        node.add(build(item))
    return node

def run_tests():
    s = Solution()

    assert s.depthSumInverse(build([[1, 1], 2, [1, 1]]).getList()) == 8

    assert s.depthSumInverse(build([1, [4, [6]]).getList()) == 17

    assert s.depthSumInverse(build([0]).getList()) == 0

    assert s.depthSumInverse(build([[-1], [2], [[3]]]).getList()) == 2

    print("all tests passed")

run_tests()

Test meaning: