You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.
The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer's value set to its depth. Let maxDepth be the maximum depth of any integer.
The weight of an integer is maxDepth - (the depth of the integer) + 1.
Return the sum of each integer in nestedList multiplied by its weight.
Example 1:
Input: nestedList = [[1,1],2,[1,1]] Output: 8 Explanation: Four 1's with a weight of 1, one 2 with a weight of 2. 1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8
Example 2:
Input: nestedList = [1,[4,[6]]] Output: 17 Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1. 1*3 + 4*2 + 6*1 = 17
Constraints:
1 <= nestedList.length <= 50[-100, 100].50.Problem Overview: You receive a nested list of integers where each element can either be a single integer or another list. The weight of each integer is determined by its depth from the bottom of the structure. Integers at the deepest level have weight 1, and the weight increases as you move toward the root. The task is to compute the total weighted sum.
Approach 1: Two-Pass DFS (O(n) time, O(d) space)
This method uses Depth-First Search to first determine the maximum depth of the nested structure. A recursive DFS walks through each element, increasing the depth when entering sublists. Once the maximum depth is known, run another DFS traversal and multiply each integer by (maxDepth - currentDepth + 1). Every element is visited twice, but the overall work remains linear. Space complexity is O(d) due to the recursion stack where d is the nesting depth.
Approach 2: BFS Level Accumulation (O(n) time, O(w) space)
A more elegant solution uses Breadth-First Search to process the structure level by level. Maintain two variables: unweighted (sum of all integers seen so far) and weighted (final result). During each level traversal, add integers to unweighted. After finishing the level, add unweighted to weighted. Because shallow integers persist across multiple levels, they effectively gain higher weights. This avoids computing maximum depth entirely while still visiting each element exactly once.
The BFS approach typically uses a queue to process lists iteratively. Each time you encounter a nested list, push its elements into the queue for the next level. This pattern is closely related to level-order traversal problems and sometimes appears with a Stack or queue depending on the implementation style.
Recommended for interviews: The BFS accumulation approach is usually the strongest answer. It solves the inverse-weight requirement without explicitly computing depth and keeps the runtime O(n) with clean logic. The two-pass DFS solution still demonstrates solid recursion and tree traversal skills, so mentioning it briefly shows broader understanding.
Let's assume the integers are a_1, a_2, cdots, a_n, their depths are d_1, d_2, cdots, d_n, the maximum depth is maxDepth, then the answer is:
$
a_1 times maxDepth - a_1 times d_1 + a_1 + a_2 times maxDepth - a_2 times d_2 + a_2 + cdots + a_n times maxDepth - a_n times d_n + a_n
which is:
(maxDepth + 1) times (a_1 + a_2 + cdots + a_n) - (a_1 times d_1 + a_2 times d_2 + cdots + a_n times d_n)
If we denote the sum of all integers as s, and the sum of each integer multiplied by its depth as ws, then the answer is:
(maxDepth + 1) times s - ws
Therefore, we design a function dfs(x, d), which starts searching from x with depth d. The execution process of dfs(x, d) is as follows:
; is an integer, then we update s = s + x, ws = ws + x times d; of x, and call dfs(y, d + 1).We traverse the entire list, for each element x, we call dfs(x, 1), and finally return (maxDepth + 1) times s - ws.
The time complexity is O(n), and the space complexity is O(n). Where n$ is the number of integers.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Two-Pass DFS | O(n) | O(d) | When recursion is preferred and computing maximum depth first makes the logic clearer |
| BFS Level Accumulation | O(n) | O(w) | Best general solution; processes levels iteratively without computing depth |
Leetcode 364 - Nested List Weight Sum II (JAVA Solution Explained!) • LC Bear • 3,742 views views
Watch 9 more video solutions →Practice Nested List Weight Sum II with our built-in code editor and test cases.
Practice on FleetCode