LeetCode 339 - Nested List Weight Sum

LeetCode Problem 339

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

Solution

Problem Understanding

This problem gives us a special nested data structure called NestedInteger. Each element in the input can either be:

1. A single integer
2. Another list containing more NestedInteger objects

The goal is to compute a weighted sum where every integer is multiplied by the depth at which it appears.

Depth starts at 1 for elements directly inside the top-level list. Every time we move one level deeper into a nested list, the depth increases by 1.

For example, consider:

[1,[4,[6]]]

The integer 1 is at depth 1, the integer 4 is at depth 2, and the integer 6 is at depth 3.

So the final answer becomes:

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

The input is represented using the NestedInteger interface. We do not implement this interface ourselves. Instead, we interact with it through the provided methods:

• isInteger() tells us whether the current object stores a single integer
• getInteger() returns that integer
• getList() returns the nested list

The constraints are relatively small:

• At most 50 elements in the top-level list
• Maximum nesting depth is 50
• Integer values range from -100 to 100

These constraints tell us that recursion is perfectly safe here because the recursion depth is bounded. They also tell us that an O(n) traversal is more than sufficient.

Several edge cases are important:

• A list may contain only one integer
• Nested lists may be deeply nested
• Values can be negative
• Empty nested lists may appear
• The result may be 0 even when elements exist

A correct solution must properly track depth while traversing all nested structures.

Approaches

Brute Force Approach

A brute force approach would repeatedly scan the nested structure level by level. One possible implementation could first flatten the structure into pairs of (value, depth) and then compute the weighted sum afterward.

For example:

[1,[4,[6]]]

could first become:

[(1,1), (4,2), (6,3)]

and then we would compute:

1*1 + 4*2 + 6*3

This works correctly because every integer is eventually discovered along with its depth. However, depending on implementation, repeatedly traversing nested structures or storing all intermediate pairs adds unnecessary work and memory usage.

The main inefficiency is that we do not actually need to store all values before computing the result. We can calculate contributions immediately during traversal.

Key Insight

The important observation is that every integer contributes independently to the final answer.

As soon as we encounter an integer, we already know:

• Its value
• Its current depth

Therefore, we can immediately add:

value * depth

to the running total.

This naturally leads to a depth-first traversal where:

• Entering a nested list increases depth
• Leaving the list decreases depth automatically through recursion

A recursive DFS solution is clean because the structure itself is recursive. Every nested list contains smaller versions of the same problem.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Flattens structure before computing result
Optimal DFS	O(n)	O(d)	Computes weighted sum during traversal

Here:

• n is the total number of nested elements
• d is the maximum depth

Algorithm Walkthrough

Optimal DFS Algorithm

1. Initialize a variable to store the total weighted sum.
2. Create a recursive helper function that accepts:

• A list of NestedInteger objects
• The current depth

3. Iterate through every element in the current list.
4. For each element:

• If it is an integer:

• Retrieve its value using getInteger()

• Multiply it by the current depth

• Add the result to the total

• Otherwise:

• Retrieve the nested list using getList()

• Recursively process that list with depth + 1

5. Start the recursion using the original nestedList and depth 1.
6. After traversal finishes, return the accumulated total.

Why it works

The algorithm works because every integer is visited exactly once at the correct recursion depth.

The recursive call maintains an invariant:

The depth parameter always matches the actual nesting level of the current list.

Whenever recursion enters a deeper nested list, depth increases by 1. Therefore, when an integer is processed, multiplying by the current depth produces exactly the required weighted contribution.

Since every nested element is traversed and every integer contributes once, the final sum is correct.

Python Solution

from typing import List

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
#     def isInteger(self) -> bool:
#         pass
#
#     def getInteger(self) -> int:
#         pass
#
#     def getList(self) -> List['NestedInteger']:
#         pass

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        def dfs(current_list: List[NestedInteger], depth: int) -> int:
            total = 0

            for nested in current_list:
                if nested.isInteger():
                    total += nested.getInteger() * depth
                else:
                    total += dfs(nested.getList(), depth + 1)

            return total

        return dfs(nestedList, 1)

The solution uses a recursive helper function named dfs.

The helper receives the current nested list and the current depth. For every element, it checks whether the element is an integer or another nested list.

If the element is an integer, its weighted contribution is immediately added to the running total.

If the element is another list, recursion processes that sublist at the next depth level.

The recursion naturally mirrors the nested structure of the input. Each recursive call handles one level of nesting independently, which keeps the implementation concise and easy to reason about.

The final call begins with depth 1 because the outermost list corresponds to depth 1.

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 {
 * }
 *
 * func (n NestedInteger) IsInteger() bool {}
 * func (n NestedInteger) GetInteger() int {}
 * func (n NestedInteger) GetList() []*NestedInteger {}
 */

func depthSum(nestedList []*NestedInteger) int {
    var dfs func([]*NestedInteger, int) int

    dfs = func(currentList []*NestedInteger, depth int) int {
        total := 0

        for _, nested := range currentList {
            if nested.IsInteger() {
                total += nested.GetInteger() * depth
            } else {
                total += dfs(nested.GetList(), depth+1)
            }
        }

        return total
    }

    return dfs(nestedList, 1)
}

The Go implementation follows the same recursive DFS strategy as the Python version.

One difference is that Go uses pointers to NestedInteger objects:

[]*NestedInteger

instead of Python object references.

The recursive helper is declared using a function variable so it can recursively reference itself.

Go slices are already dynamic references to underlying arrays, so passing nested lists into recursive calls is efficient.

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

Worked Examples

Example 1

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

Traversal Process

Step	Element	Depth	Contribution	Running Total
1	[1,1]	1	recurse	0
2	1	2	1 × 2 = 2	2
3	1	2	1 × 2 = 2	4
4	2	1	2 × 1 = 2	6
5	[1,1]	1	recurse	6
6	1	2	1 × 2 = 2	8
7	1	2	1 × 2 = 2	10

Final answer:

10

Example 2

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

Traversal Process

Step	Element	Depth	Contribution	Running Total
1	1	1	1 × 1 = 1	1
2	[4,[6]]	1	recurse	1
3	4	2	4 × 2 = 8	9
4	[6]	2	recurse	9
5	6	3	6 × 3 = 18	27

Final answer:

27

Example 3

nestedList = [0]

Traversal Process

Step	Element	Depth	Contribution	Running Total
1	0	1	0 × 1 = 0	0

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every nested element is visited exactly once
Space	O(d)	Recursive call stack stores at most one frame per depth level

The traversal processes each integer and nested list exactly once, so the runtime grows linearly with the total number of elements.

The auxiliary space comes entirely from recursion depth. In the worst case, the input may be nested up to depth d, which creates d recursive stack frames.

Test Cases

# Helper utilities for local testing only
# These are NOT part of the LeetCode submission.

class NestedInteger:
    def __init__(self, value=None):
        if value is None:
            self.value = []
        else:
            self.value = value

    def isInteger(self):
        return isinstance(self.value, int)

    def getInteger(self):
        return self.value

    def getList(self):
        return self.value

    def add(self, elem):
        self.value.append(elem)

class Solution:
    def depthSum(self, nestedList):
        def dfs(current_list, depth):
            total = 0

            for nested in current_list:
                if nested.isInteger():
                    total += nested.getInteger() * depth
                else:
                    total += dfs(nested.getList(), depth + 1)

            return total

        return dfs(nestedList, 1)

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

    nested = NestedInteger()

    for item in data:
        nested.add(make_nested(item))

    return nested

sol = Solution()

# Example 1
case1 = [make_nested([1, 1]), make_nested(2), make_nested([1, 1])]
assert sol.depthSum(case1) == 10  # standard mixed nesting example

# Example 2
case2 = [make_nested(1), make_nested([4, [6]])]
assert sol.depthSum(case2) == 27  # increasing nesting depth

# Example 3
case3 = [make_nested(0)]
assert sol.depthSum(case3) == 0  # single zero element

# Single integer
case4 = [make_nested(5)]
assert sol.depthSum(case4) == 5  # depth 1 only

# Deep nesting
case5 = [make_nested([[[1]]])]
assert sol.depthSum(case5) == 4  # integer at depth 4

# Negative numbers
case6 = [make_nested([-1, [-2]])]
assert sol.depthSum(case6) == -5  # negative weighted contributions

# Empty nested list
case7 = [make_nested([])]
assert sol.depthSum(case7) == 0  # empty structures contribute nothing

# Multiple branches
case8 = [
    make_nested([1, [2]]),
    make_nested([[3], 4])
]
assert sol.depthSum(case8) == 21  # mixed branching depths

Test	Why
[[1,1],2,[1,1]]	Standard example with multiple nested lists
[1,[4,[6]]]	Verifies increasing recursive depth
[0]	Ensures zero values are handled correctly
[5]	Simplest non-nested input
[[[1]]]	Tests deep recursion
[-1,[-2]]	Confirms negative numbers work correctly
[[]]	Ensures empty nested lists do not break traversal
[[1,[2]],[[3],4]]	Tests multiple recursive branches

Edge Cases

Deeply Nested Structures

An input like:

[[[[[1]]]]]

can easily expose bugs in depth tracking. A solution that forgets to increment depth during recursion would produce the wrong weighted contribution.

This implementation handles the case correctly because every recursive call explicitly uses:

depth + 1

which guarantees accurate nesting levels.

Empty Nested Lists

Nested structures may contain empty lists such as:

[[],[[]]]

A naive implementation might incorrectly assume every nested list contains integers.

This solution safely handles empty lists because iterating over an empty list simply performs no work and contributes 0 to the total.

Negative Values

The problem allows integers in the range:

[-100, 100]

Negative values can produce negative weighted sums.

For example:

[-1,[-2]]

produces:

(-1 * 1) + (-2 * 2) = -5

This implementation handles negative numbers naturally because multiplication and addition work identically for positive and negative integers.

Single Top-Level Integer

An input containing only one integer:

[7]

is important because the algorithm must still treat the top-level depth as 1.

The solution begins recursion with:

dfs(nestedList, 1)

which guarantees correct weighting for top-level integers.