Watch 10 video solutions for Nested List Weight Sum II, a medium level problem involving Stack, Depth-First Search, Breadth-First Search. This walkthrough by LC Bear has 3,742 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |