339. Nested List Weight Sum

339

MediumGraph DFS and BFSDFSDepth-weighted recursion over nested structure

Nested List Weight Sum

You are given a nested list of integers where each element is either a single integer or a list whose elements may themselves be integers or lists. The depth of an integer is the number of lists that contain it, starting at 1 for the outermost level. Return the sum of every integer multiplied by its depth.

Open official problem prompt ↗

In plain English

Add up every integer in an arbitrarily nested list, but weight each one by how many lists enclose it.

Picture it like this

Think of a company org chart: an employee's influence counts more the deeper their department is nested. You walk down each branch, and the further you descend, the higher the multiplier on the numbers you find there.

Example

Input: nestedList = [[1,1],2,[1,1]]
Output: 10
Why: Four 1's sit at depth 2 and the 2 sits at depth 1, so 4*(1*2) + 1*(2*1) = 8 + 2 = 10.

Constraints

1 <= nestedList.length <= 50The values of the integers are in the range [-100, 100]The maximum depth of any integer is <= 50

Pattern lesson

See the pattern, then code

Depth-weighted recursion over nested structure

↗

Graph DFS and BFS

Connected components, grids, reachability, or unweighted shortest paths.. Treat the nesting as a tree: each list is an internal node and each integer is a leaf. Recurse into each sublist while incrementing the depth counter, and add value*depth for every integer you reach.

New words, made simpleKnow these before the algorithm

NestedInteger: The provided interface: it either holds a single integer (isInteger/getInteger) or a list of NestedIntegers (getList).
Depth: How many lists wrap a given integer; the outermost level is depth 1.
Recursion depth: How many nested helper calls are active at once, bounded by the deepest nesting.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Flatten then re-scan

Correct but does two passes and materializes an intermediate list needlessly.

First flatten into (value, depth) pairs, then sum. Requires an extra pass and extra storage.

Time O(n)Space O(n)

Best choiceDFS carrying depth

Single pass, memory only the recursion stack up to the maximum depth.

Recurse through the structure, passing the current depth down and adding value*depth at each integer in a single pass.

Time O(n)Space O(d)

The rule we keep true

Invariant

When the helper is invoked on a list, its depth argument equals exactly the number of lists that enclose every integer directly inside that list.

Why this is correct

Reasoning

Every integer is visited exactly once, and at the moment it is visited the depth parameter has been incremented once per enclosing list, so value*depth is precisely its contribution. Summing all contributions gives the answer.

The algorithm in three movesSay these aloud before coding

1Write a helper that takes a list and the current depth

depth=1: see [1,1] -> recurse depth=2

2For each item, if it is an integer add value*depth

depth=2: 1*2 + 1*2 = 4

3If it is a list, recurse into it with depth+1

depth=1: 2*1 = 2; final 4+2+4 = 10

4Start the helper at the top level with depth 1

5Return the accumulated total

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

[1,1]0

[1,1]2

1 · Read[[1,1], 2, [1,1]]

2 · AskFor each item, integer or list?

3 · Update statedepth=1, total=0

4 · ResultFirst item is a list -> recurse at depth 2

Key takeaway

The two bracketed sublists are explored at depth 2 while the bare 2 contributes at depth 1.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Helper header
dfs takes the current list and the depth that applies to its direct integer children.
2
Lines 6-8Integer case
A leaf integer contributes its value scaled by the current depth.
3
Lines 9-10List case
A nested list is explored one level deeper, so recurse with depth+1.
4
Lines 12Kick-off
The outermost list starts at depth 1.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

A single flat list like [1,2,3] where everything is depth 1
Deeply nested single chains such as [[[[5]]]]
Negative integers, which reduce the total
Empty sublists like [[],3] that contribute nothing

Common beginner mistakes

Starting depth at 0 instead of 1, which zeroes out the outermost integers
Forgetting to increment depth when descending into a sublist
Calling getInteger on a list node or getList on an integer node without checking isInteger first

Check your understanding

How would you switch this to a BFS solution, and would the answer change?

Nested List Weight Sum

Nested List Weight Sum

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Graph DFS and BFS