Nested List Weight Sum II
Asked at LinkedIn
Problem
Nested List Weight Sum II gives you a nested list of integers and asks for the sum of each integer multiplied by its weight, where the weight is maxDepth - depth + 1 — so the deepest integers count once and the top-level integers count the most. The neat solution avoids computing the maximum depth first.
Asked At
| Company | Difficulty | |
|---|---|---|
| Medium | View all LinkedIn questions → |
How to Think About It
Two-pass approach: first find maxDepth, then do a second pass summing value * (maxDepth - depth + 1). That is correct and O(n).
Key insight for one pass: go level by level (BFS). Keep levelSum, the running sum of all integers seen so far. After each level, add levelSum to the answer.
Why it works: an integer at depth d stays in levelSum for every level from d down to the last one, so it gets added exactly maxDepth - d + 1 times — which is exactly its weight.
Walkthrough for [[1,1],2,[1,1]]: level 1 integers 2 -> levelSum 2, total 2. Level 2 integers 1,1,1,1 -> levelSum 6, total 8. Answer 8.
Equivalent formula if you prefer one DFS: (maxDepth + 1) * sum(values) - sum(value * depth).
Optimal Approach
Step 1: level = nestedList, levelSum = 0, total = 0.
Step 2: While level is not empty:
nxt = []
For each item: if it is an integer, add it to levelSum; otherwise extend nxt with its list.
total += levelSum
level = nxt
Step 3: Return total.
Every integer and every list is visited once.
Time: O(n). Space: O(w) for the widest level.
What Trips People Up in Real Interviews
Confusing this with Nested List Weight Sum I, where weight equals depth. Here weight is inverted: the deepest level has weight 1.
Resetting levelSum every level. The running sum must carry over — that accumulation is what applies the inverse weights.
Assuming maxDepth is known up front. If you use the two-pass method, say so; if you use the one-pass trick, explain why each value is counted the right number of times.
Forgetting empty inner lists like [[]]. They contribute nothing but can still add depth.
Solution Code
def depthSumInverse(nestedList):
level = nestedList
level_sum = total = 0
while level:
nxt = []
for item in level:
if item.isInteger():
level_sum += item.getInteger()
else:
nxt.extend(item.getList())
total += level_sum
level = nxt
return totalFrequently Asked Questions
What is the Nested List Weight Sum II problem?
Nested List Weight Sum II gives you a nested list of integers and asks for the sum of each integer multiplied by its weight, where the weight is `maxDepth - depth + 1` — so the deepest integers count once and the top-level integers count the most. The neat solution avoids computing the maximum depth first.
How do you solve Nested List Weight Sum II?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Nested List Weight Sum II?
Nested List Weight Sum II is asked at LinkedIn. It is a medium difficulty problem.
What are common mistakes on Nested List Weight Sum II?
- Confusing this with Nested List Weight Sum I, where weight equals depth. Here weight is inverted: the deepest level has weight 1.
- Resetting `levelSum` every level. The running sum must carry over — that accumulation is what applies the inverse weights.
- Assuming `maxDepth` is known up front. If you use the two-pass method, say so; if you use the one-pass trick, explain why each value is counted the right number of times.
- Forgetting empty inner lists like `[[]]`. They contribute nothing but can still add depth.