Nested List Weight Sum II

Table of Contents +

Nested List Weight Sum II flips the first version on its head. Now the deepest numbers count the least, and the numbers near the surface count the most. That sounds like a tiny change. But it forces a new trick, because you do not know the top weight until you have seen the whole structure first. The interviewer is checking if you can handle that.

🎯 The Problem

You still get a nested list, which is a list that holds numbers and other lists inside it. Each number has a weight, but here the weight is inverted.

  • In the first version, deeper meant heavier. Here deeper means lighter.
  • The deepest level gets weight 1. The level above it gets weight 2. And so on, up to the top.
  • The formula is weight = maxDepth - depth + 1.
  • Here maxDepth is the deepest level in the whole structure.
  • The catch: you cannot weight the top number until you know how deep the whole thing goes.
Input:  [[1, 1], 2, [1, 1]]
Output: 8


Explanation:
- The deepest level here is 2, so maxDepth = 2.
- The four 1's sit at depth 2, so their weight is 2 - 2 + 1 = 1.
- The single 2 sits at depth 1, so its weight is 2 - 1 + 1 = 2.
- Sum = (1*1)*4 + (2*2) = 4 + 4 = 8

Here is the same tree, but now look at the weights. The shallow 2 is the heavy one. The deep 1s are the light ones. This first diagram shows that the weight grows as you climb toward the surface.

top list depth 1, weight 2

inner list depth 2

2 -> weight 2

inner list depth 2

1 -> weight 1

1 -> weight 1

1 -> weight 1

1 -> weight 1

So the catch is clear. To weight the top number you must already know how deep the whole thing goes. You cannot know that until you have looked at everything.

🐢 Approach 1: Two Passes (Brute Force)

The idea in one line: walk once to find the deepest level, then walk again to weight every number.

The idea:

  • First walk finds the deepest level. Call it maxDepth.
  • Second walk weights each number with maxDepth - depth + 1.

How it works:

  • Go all the way down and remember the largest depth reached.
  • Now you know maxDepth.
  • Walk again and add number * (maxDepth - depth + 1) for every number.

Why it is weak:

  • You touch the whole structure twice.
  • It works and is easy to explain.
  • But the interviewer may ask for a single walk.

Here is the two-pass code:

nested_list_weight_sum_ii_two_pass.py
def depth_sum_inverse(nested_list):
    values = []


    def dfs(items, depth):
        for item in items:
            if item.isInteger():
                values.append((item.getInteger(), depth))
            else:
                dfs(item.getList(), depth + 1)


    dfs(nested_list, 1)
    max_depth = max(depth for value, depth in values)
    return sum(value * (max_depth - depth + 1) for value, depth in values)

⚡ Approach 2: One Pass With a Running Sum (Best)

The idea in one line: carry a running sum of shallow numbers and add it at every level, so each number is counted the right number of times.

The idea:

  • A number at depth d with max depth D has weight D - d + 1.
  • That weight equals counting it once on its level, then once more on each level above.
  • So a running sum carried forward gives every number its inverse weight for free.

How it works:

  • Keep two totals: unweighted and weighted.
  • unweighted is the plain sum of all numbers seen so far.
  • weighted is the answer we are building.
  • At each level, add that level’s numbers to unweighted.
  • Then add the whole unweighted total into weighted.

Why it is fast:

  • One walk, no maxDepth needed.
  • Shallow numbers ride in unweighted and get added again at every deeper level.
  • That repeated adding is exactly the inverse weight.

This second diagram shows the one-pass flow. The shallow numbers ride along in unweighted and keep getting added to weighted at every level.

level 1: add 2 to unweighted (=2)

add unweighted to weighted (weighted=2)

level 2: add 1+1+1+1 to unweighted (=6)

add unweighted to weighted (weighted=2+6=8)

no deeper levels

answer = 8

Steps to Solve

  1. Keep two totals: weighted starting at zero, and unweighted starting at zero.
  2. Process the structure one level at a time, from the top down.
  3. At each level, add every plain number on that level into unweighted.
  4. After adding this level’s numbers, add the whole unweighted total into weighted.
  5. Move to the next deeper level and repeat.
  6. When there are no deeper levels, weighted holds the answer.

This Python version shows the smart one-pass method using a running unweighted sum carried forward level by level.

nested_weight_sum_ii.py
def depth_sum_inverse(nested):
    weighted = 0       # the answer we build
    unweighted = 0     # sum of numbers seen so far, carried forward
    level = nested     # the items at the current level


    while level:
        next_level = []
        for item in level:
            if isinstance(item, list):     # a deeper list
                next_level.extend(item)    # save its items for the next level
            else:                          # a plain number
                unweighted += item         # add it to the carried sum
        weighted += unweighted             # add carried sum once per level
        level = next_level                 # move one level deeper


    return weighted




data = [[1, 1], 2, [1, 1]]
print(depth_sum_inverse(data))

The output of the above code will be:

8

Let us walk through the Python one-pass version line by line, because the carried sum is the clever part.

weighted = 0
unweighted = 0
level = nested

weighted is the final answer. unweighted is the plain sum of every number we have met so far, with no depth applied. level holds the items sitting at the level we are processing right now. We start at the top list.

while level:
    next_level = []

We keep going as long as the current level has items. We also prepare an empty next_level list to collect everything one level deeper.

    for item in level:
        if isinstance(item, list):
            next_level.extend(item)
        else:
            unweighted += item

We look at each item on this level. If it is a list, we do not sum it. We just push its contents into next_level to deal with later. If it is a plain number, we add it to unweighted. So unweighted now holds every number from the top down to this level.

    weighted += unweighted

This is the trick. We add the whole unweighted total into weighted once per level. Because unweighted carries forward and keeps growing, a shallow number gets added again at every level below it. A number at the top is added once for its own level, then once more for every level beneath. That repeated adding is exactly its inverse weight, with no maxDepth needed.

    level = next_level
return weighted

We move down to the next level and repeat. When no deeper level is left, weighted is the full inverse-weighted sum. So one walk does it. We never needed two passes.

⏱️ Time and Space Complexity

The two-pass way walks everything twice, but two times n is still O(n) time. The one-pass way walks everything once, also O(n) time. The space for both is the cost of holding a level or the recursion stack, which in the worst case is O(n). So the one-pass version is not faster in big-O terms. It is just neater, and it answers the interviewer’s “can you do it in a single pass” with a confident yes. That single pass is the part worth showing.

Approach Time Complexity Space Complexity
Two passes (find max depth, then sum) O(n) O(d)
One pass (carried running sum) O(n) O(n)

Tip

The line to say out loud is that a shallow number gets counted once for every level below it. That repeated counting equals the inverse weight, which is why the running sum trick removes the need to know maxDepth first.

🧩 Key Takeaways

  • ✅ Here the weight is inverted, so the deepest numbers count the least and the shallowest count the most.
  • ✅ The simple way is two passes: find the max depth, then weight each number by maxDepth - depth + 1.
  • ✅ The smart way is one pass: keep a running unweighted sum and add it into weighted at every level.
  • ✅ A shallow number is added once per level below it, which equals its inverse weight automatically.
  • ✅ Both run in O(n) time, but the one-pass answer is what impresses in an interview.

Check Your Knowledge

 4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

  1. 1

    How does the weight differ from the first Nested List Weight Sum problem?

    Why: In part one, deeper meant heavier. In part two, the weight is maxDepth - depth + 1, so deeper means lighter.

  2. 2

    Why does the simple solution need two passes?

    Why: The weight depends on maxDepth, and you only know maxDepth after walking the whole structure once.

  3. 3

    In the one-pass trick, why is the unweighted sum added at every level?

    Why: Carrying the running sum forward and adding it each level counts shallow numbers repeatedly, exactly matching the inverse weight.

  4. 4

    What is the time complexity of the one-pass solution?

    Why: The one-pass method visits every item once, so it is linear, O(n).

Score: 0 / 4

🚀 What’s Next?

Previous Nested List Weight Sum Next Dot Product of Two Sparse Vectors