LeetCode 364 - Nested List Weight Sum II

Difficulty: 🟡 Medium
Topics: Stack, Depth-First Search, Breadth-First Search

Solution

Problem Understanding

The problem gives us a nested list structure where each element can either be:

A single integer
Another nested list containing additional integers or lists

The goal is to compute a weighted sum of all integers, but unlike the standard "Nested List Weight Sum" problem, the weighting is inverted.

Normally, deeper integers receive larger weights. In this problem, shallower integers receive larger weights.

If an integer appears at depth d, and the maximum depth anywhere in the structure is maxDepth, then its weight is:

$\text{weight} = \text{maxDepth} - d + 1$

This means:

Integers at the deepest level get weight 1
Integers one level above get weight 2
Integers near the root receive the largest weight

For example, consider:

[1,[4,[6]]]

The depths are:

1 at depth 1
4 at depth 2
6 at depth 3

The maximum depth is 3, so the weights become:

1 -> weight 3
4 -> weight 2
6 -> weight 1

The final answer is:

1*3 + 4*2 + 6*1 = 17

The input size is relatively small:

At most 50 top-level elements
Maximum nesting depth is at most 50
Integer values range from -100 to 100

These constraints tell us that recursion is perfectly safe because recursion depth will never exceed 50. Time efficiency still matters, but we do not need extremely advanced optimizations.

Several edge cases are important:

A structure containing only one integer
Very deeply nested lists
Negative integers
Multiple lists at different depths
All integers appearing at the same depth
Nested lists containing only one child repeatedly

The problem also guarantees there are no empty lists, which simplifies traversal logic because every list contains at least one element.

Approaches

Brute Force Approach

The most direct solution is a two-pass depth-first traversal.

In the first traversal, we compute the maximum depth of the nested structure. Every time we recurse into another list, we increase the depth counter. Whenever we encounter an integer, we update the global maximum depth if necessary.

Once we know the maximum depth, we perform a second traversal. During this traversal, we again track the current depth. For each integer, we compute its weight using:

$\text{contribution} = \text{value} \times (\text{maxDepth} - d + 1)$

We then add the contribution to the final answer.

This approach is correct because every integer's contribution depends on the global maximum depth, which we discover in the first pass.

Although this approach is efficient enough for the constraints, it traverses the entire structure twice.

Optimal Approach

A more elegant solution uses breadth-first traversal and avoids explicitly calculating weights.

The key insight is that inverse weighting can be simulated cumulatively.

Suppose we process the nested list level by level:

At each level, we add all integers found at that level to an unweighted running sum.
After processing a level, we add unweighted into the final answer.

Why does this work?

Integers at shallow depths remain in unweighted for more levels, so they are added multiple times. Integers at deeper levels appear later and therefore contribute fewer times.

This naturally reproduces inverse depth weighting without explicitly computing maximum depth.

For example:

[1,[4,[6]]]

Level processing:

Level 1:
unweighted = 1
answer += 1
Level 2:
unweighted = 1 + 4 = 5
answer += 5
Level 3:
unweighted = 5 + 6 = 11
answer += 11

Final answer:

1 + 5 + 11 = 17

Notice:

1 contributed three times
4 contributed two times
6 contributed one time

Exactly the required inverse weights.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(N)	O(D)	Two DFS traversals, first for max depth, second for weighted sum
Optimal	O(N)	O(W)	BFS level traversal using cumulative sums

Here:

N is the total number of nested elements and integers
D is maximum depth
W is maximum width of a level during BFS

Algorithm Walkthrough

Optimal BFS Algorithm

Initialize three variables:

unweighted = 0
weighted = 0
current_level = nestedList

The unweighted variable stores the cumulative sum of all integers seen so far. The weighted variable stores the final answer. 2. Begin a loop while the current level is not empty.

Each iteration processes one depth level of the nested structure. 3. Create an empty list called next_level.

This will store all nested lists that belong to the next depth level. 4. Traverse every element in current_level.

For each element:

If it is an integer, add its value to unweighted
If it is a list, append all its children into next_level

After finishing the level, add unweighted into weighted.

This is the crucial insight.

Every integer discovered so far contributes once for every remaining level, automatically creating inverse depth weighting. 6. Replace current_level with next_level.

This advances the BFS traversal to the next depth. 7. Continue until all levels are processed. 8. Return weighted.

Why it works

The invariant is that unweighted always contains the sum of every integer discovered up to the current depth.

Each BFS level adds unweighted into the answer once. Therefore:

Shallow integers remain in unweighted for many iterations
Deep integers remain for fewer iterations

An integer at depth d contributes exactly:

maxDepth - d + 1

times, which matches the required inverse weight definition.

Python Solution

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def __init__(self, value=None):
#        pass
#
#    def isInteger(self):
#        pass
#
#    def add(self, elem):
#        pass
#
#    def setInteger(self, value):
#        pass
#
#    def getInteger(self):
#        pass
#
#    def getList(self):
#        pass

from typing import List

class Solution:
    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
        unweighted_sum = 0
        weighted_sum = 0
        
        current_level = nestedList
        
        while current_level:
            next_level = []
            
            for nested in current_level:
                if nested.isInteger():
                    unweighted_sum += nested.getInteger()
                else:
                    next_level.extend(nested.getList())
            
            weighted_sum += unweighted_sum
            current_level = next_level
        
        return weighted_sum

The implementation closely follows the BFS algorithm described earlier.

The variable current_level stores all nodes at the current depth. During traversal, integers immediately contribute to unweighted_sum, while child lists are collected into next_level.

The key observation appears in this line:

weighted_sum += unweighted_sum

This causes shallow integers to contribute repeatedly across multiple levels.

The algorithm terminates naturally once there are no more nested lists to process.

The implementation is iterative, avoids recursion entirely, and uses only simple list operations.

Go Solution

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * type NestedInteger struct {
 * }
 *
 * // Return true if this NestedInteger holds a single integer, rather than a nested list.
 * func (n NestedInteger) IsInteger() bool {}
 *
 * // Return the single integer that this NestedInteger holds, if it holds a single integer
 * func (n NestedInteger) GetInteger() int {}
 *
 * // Set this NestedInteger to hold a single integer.
 * func (n *NestedInteger) SetInteger(value int) {}
 *
 * // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 * func (n *NestedInteger) Add(elem NestedInteger) {}
 *
 * // Return the nested list that this NestedInteger holds, if it holds a nested list
 * func (n NestedInteger) GetList() []*NestedInteger {}
 */

func depthSumInverse(nestedList []*NestedInteger) int {
    unweightedSum := 0
    weightedSum := 0

    currentLevel := nestedList

    for len(currentLevel) > 0 {
        nextLevel := []*NestedInteger{}

        for _, nested := range currentLevel {
            if nested.IsInteger() {
                unweightedSum += nested.GetInteger()
            } else {
                nextLevel = append(nextLevel, nested.GetList()...)
            }
        }

        weightedSum += unweightedSum
        currentLevel = nextLevel
    }

    return weightedSum
}

The Go implementation mirrors the Python solution almost exactly.

Slices are used to represent BFS levels. The expression:

append(nextLevel, nested.GetList()...)

appends all children from a nested list into the next BFS layer.

Unlike Python, Go requires explicit slice initialization and pointer handling because GetList() returns []*NestedInteger.

Integer overflow is not a concern because the constraints are very small.

Worked Examples

Example 1

Input:

[[1,1],2,[1,1]]

BFS Traversal State

Level	Integers Found	unweighted_sum	weighted_sum
1	2	2	2
2	1,1,1,1	6	8

Final answer:

Explanation:

The integer 2 contributes twice
Each 1 contributes once

So:

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

Example 2

Input:

[1,[4,[6]]]

BFS Traversal State

Level	Integers Found	unweighted_sum	weighted_sum
1	1	1	1
2	4	5	6
3	6	11	17

Final answer:

Contribution breakdown:

1 added three times
4 added two times
6 added once

Equivalent to:

1*3 + 4*2 + 6*1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(N)	Every integer and nested list is processed exactly once
Space	O(W)	BFS queue stores one level at a time

N represents the total number of nested elements, including integers and lists.

The BFS traversal visits every node exactly once, so runtime is linear.

The auxiliary space depends on the maximum width of the nested structure because one BFS level is stored at a time.

Test Cases

# Provided example 1
assert Solution().depthSumInverse([[1,1],2,[1,1]]) == 8

# Provided example 2
assert Solution().depthSumInverse([1,[4,[6]]]) == 17

# Single integer
assert Solution().depthSumInverse([5]) == 5

# Deep nesting with one value
assert Solution().depthSumInverse([[[[[1]]]]]) == 1

# All integers at same depth
assert Solution().depthSumInverse([[1,2],[3,4]]) == 10

# Negative numbers
assert Solution().depthSumInverse([1,[-2,[3]]]) == 2

# Multiple nested branches
assert Solution().depthSumInverse([[1,[2]],3,[4,[5,[6]]]]) == 40

# Maximum shallow weighting
assert Solution().depthSumInverse([10,[1],[1],[1]]) == 23

# Nested negatives
assert Solution().depthSumInverse([[-1],[-2,[-3]]]) == -10

# Long chain nesting
assert Solution().depthSumInverse([[[[[[7]]]]]]) == 7

Test Summary

Test	Why
`[[1,1],2,[1,1]]`	Validates standard inverse weighting
`[1,[4,[6]]]`	Verifies multiple depth levels
`[5]`	Smallest valid input
`[[[[[1]]]]]`	Deep nesting edge case
`[[1,2],[3,4]]`	Same-depth integers
`[1,[-2,[3]]]`	Negative number handling
`[[1,[2]],3,[4,[5,[6]]]]`	Complex branching structure
`[10,[1],[1],[1]]`	Ensures shallow nodes receive larger weights
`[[-1],[-2,[-3]]]`	Negative weighted accumulation
`[[[[[[7]]]]]]`	Deep recursive-style nesting

Edge Cases

Single Integer Input

A structure like:

[5]

is important because the maximum depth is 1. The integer should receive weight 1, not some larger value.

The BFS implementation handles this naturally because only one level exists, so unweighted_sum is added into weighted_sum exactly once.

Very Deep Nesting

An input such as:

[[[[[1]]]]]

can expose recursion issues in DFS implementations if recursion depth is not carefully managed.

The iterative BFS solution avoids recursion entirely, making it robust even for deeply nested inputs.

Negative Integers

Negative values can expose bugs where implementations incorrectly assume all contributions are positive.

For example:

[1,[-2,[3]]]

requires proper weighted accumulation with both positive and negative values.

Because the algorithm only performs arithmetic accumulation without any assumptions about sign, negative values are handled correctly automatically.