MediumStackDepth-First SearchBreadth-First SearchUpdated Sep 2026

364. Nested List Weight Sum II

Asked at LinkedIn

Difficulty

Medium

Time

O(n)

Space

O(w)

Pattern

Stack

Companies

1

Problem

You get a nested list of integers. Each element is either a plain integer, or a list that may itself contain integers and more lists.

The depth of an integer is how many lists sit around it. An integer written directly at the top level has depth 1. An integer inside one list has depth 2, and so on. Let maxDepth be the largest depth of any integer in the input.

The weight of an integer is maxDepth - depth + 1. So the deepest integers get weight 1, and the top-level integers get the biggest weight. Return the sum of every integer multiplied by its own weight.

Deep items count less

[1,1]2[1,1]012Top level (depth 1): only the 2 lives here, weight = 211110123Depth 2: the four 1's, each weight = 1
Depth 1 items get the biggest weight, depth 2 items get weight 1, so the answer is 2*2 + four 1's*1 = 8.

Constraints

  • ●1 <= nestedList.length <= 50
  • ●-100 <= value of each integer <= 100
  • ●The maximum depth of any integer is at most 50
  • ●There are no empty lists

Examples

Example 1
InputnestedList = [[1,1],2,[1,1]]
Output8
WhyThe 2 sits at depth 1 and the four 1's sit at depth 2, so maxDepth is 2. The 2 gets weight 2 and each 1 gets weight 1: 2*2 + 1*1 + 1*1 + 1*1 + 1*1 = 8.
Example 2
InputnestedList = [1,[4,[6]]]
Output17
WhyThe 6 is the deepest at depth 3, so maxDepth is 3. Weights are 3 for the 1, 2 for the 4 and 1 for the 6: 1*3 + 4*2 + 6*1 = 17.

Asked At

1 companies
CompanyDifficulty
LinkedInMediumView all LinkedIn questions →

How to Think About It

1

Two-pass approach: first find maxDepth, then do a second pass summing value * (maxDepth - depth + 1). That is correct and O(n).

2

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.

3

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.

4

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.

5

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.

One BFS pass, add the running sum each level

level 1[1,1]2[1,1]frontbackLevel 1: only the 2 is an integer, so levelSum = 2 andtotal = 2level 21111frontbackLevel 2: four 1's arrive, levelSum becomes 2 + 4 = 6,total = 2 + 6 = 8levelSum += integers on this leveltotal += levelSumanswer = 8
After each level we add levelSum to the total, so an item at depth d is counted once for every level from d to the bottom.
ComplexityTime O(n)Space O(w)Every integer and every list is touched once; w is the number of items on the widest level, which is the largest queue we hold.

What Trips People Up in Real Interviews

1

Confusing this with Nested List Weight Sum I, where weight equals depth. Here weight is inverted: the deepest level has weight 1.

2

Resetting levelSum every level. The running sum must carry over — that accumulation is what applies the inverse weights.

3

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.

4

Forgetting empty inner lists like [[]]. They contribute nothing but can still add depth.

Solution Code

O(n) time
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 total

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently 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 runs in O(n) time and O(w) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.