Nested List Weight Sum II

Nested List Weight Sum II

What is this problem about?

The Nested List Weight Sum II problem inverts the weighting from Nested List Weight Sum I. Now deeper integers have higher weights — a number at depth d gets multiplied by (maxDepth - d + 1) instead of d. This Nested List Weight Sum II coding problem requires either finding the maximum depth first or using a clever BFS reverse-accumulation trick.

Why is this asked in interviews?

Meta, Amazon, LinkedIn, and Google ask this as a follow-up to the first variant. It tests adaptability — the same structure with an inverted weighting requires a different approach or an extra pass. The BFS, DFS, and stack interview pattern is exercised, and the elegant one-pass BFS trick (accumulating sums level by level and adding the running sum for each level) is particularly impressive.

Algorithmic pattern used

BFS with running sum accumulation. Process the nested list level by level using BFS. For each level, compute the sum of all integers at that level. Maintain a runningSum that accumulates all integer sums seen so far. After processing each level, add runningSum to the total result. This effectively multiplies each integer by its "levels remaining below it" without knowing maxDepth in advance.

Example explanation

List: [[1,1],2,[1,1]]. Depths: depth 1 → integers at root level = 2; depth 2 → integers inside lists = 1,1,1,1. Max depth = 2. Weights: depth-1 integers get weight 2, depth-2 get weight 1.

• 2 (depth 1) * 2 = 4.
• 1,1,1,1 (depth 2) * 1 = 4. Total = 4+4 = 8.

BFS trick: level 1 sum = 2, running=2. level 2 sum = 4, running=6. Result = 2+6=8. ✓

Common mistakes candidates make

• Computing max depth first, then doing a second DFS (correct but two-pass).
• Applying the same depth formula as Nested List Weight Sum I (wrong direction).
• Not understanding the BFS running sum trick (it's non-obvious on first encounter).
• Handling leaf integers vs inner-list integers differently.

Interview preparation tip

The "reverse weight" BFS trick is elegant: accumulate levelSum per BFS level, maintain a runningSum that grows each level, and add runningSum to the result at the end of each level. This automatically gives deeper elements lower weight (they contribute to fewer runningSum additions). Understanding this trick shows creative thinking and is a strong differentiator in Meta and Google interviews. Practice deriving it from scratch rather than memorizing.