Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 364. Nested List Weight Sum II

Given a nested list of integers, compute the sum where each integer is weighted by the reverse of its depth (elements deeper in the nesting get smaller weights, weight = maxDepth − depth + 1). The challenge is handling arbitrary nesting and determining appropriate weights across levels to produce the weighted total.

Asked at:

DESCRIPTION

Input:

nestedList = [1,[4,[6]]]

Output:

Explanation: Maximum depth is 3. Weighted sum: 13 + 42 + 6*1 = 3 + 8 + 6 = 17

Constraints:

1 <= nestedList.length <= 50
The values of the integers in the nested list are in the range [-100, 100]
The maximum depth of any integer is less than or equal to 50
Each element is either an integer or a list whose elements are also integers or other lists

Understanding the Problem

Let's understand what we're being asked to do. We have a nested list like [1,[4,[6]]] where integers can be at different depths.

Tracing through the structure: 1 is at depth 1 (outermost level), 4 is at depth 2 (inside one list), and 6 is at depth 3 (inside two nested lists).

Important constraint: We need to weight each integer by the reverse of its depth. If the maximum depth is 3, then depth 1 gets weight 3-1+1=3, depth 2 gets weight 3-2+1=2, and depth 3 gets weight 3-3+1=1.

For [1,[4,[6]]]: 1*3 + 4*2 + 6*1 = 3 + 8 + 6 = 17.

Edge cases to consider: What if the list is empty? What if all integers are at the same depth? What if there's only one integer? How do we handle arbitrarily deep nesting?

Brute Force Approach

The straightforward approach uses two separate DFS traversals. First traversal: recursively explore the entire nested structure to find the maximum depth by tracking the current depth at each level. Second traversal: recursively traverse again, this time calculating the weighted sum using the formula value * (maxDepth - currentDepth + 1) for each integer encountered. This approach is simple to understand but requires visiting every element twice.

Visualization

def depthSumInverse(nestedList):
    """
    Compute weighted sum where weight = maxDepth - depth + 1.
    Uses two DFS passes: first to find max depth, second to calculate sum.
    """
    # First DFS: Find maximum depth
    def findMaxDepth(nested, depth):
        maxDepth = depth
        for item in nested:
            if isinstance(item, list):
                maxDepth = max(maxDepth, findMaxDepth(item, depth + 1))
        return maxDepth
    
    # Second DFS: Calculate weighted sum
    def calculateWeightedSum(nested, depth, maxDepth):
        total = 0
        for item in nested:
            if isinstance(item, list):
                # Recursively process nested list
                total += calculateWeightedSum(item, depth + 1, maxDepth)
            else:
                # Calculate weight: maxDepth - depth + 1
                weight = maxDepth - depth + 1
                total += item * weight
        return total
    
    # First traversal: find max depth
    maxDepth = findMaxDepth(nestedList, 1)
    
    # Second traversal: calculate weighted sum
    result = calculateWeightedSum(nestedList, 1, maxDepth)
    
    return result

Start: Compute weighted sum with reverse depth

0 / 17

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We traverse all n elements twice (once to find max depth, once to calculate sum), resulting in O(2n) = O(n) time complexity

Space Complexity: O(d) The recursion stack depth is proportional to the maximum nesting depth d, which can be at most n in the worst case of deeply nested single elements

Building Intuition

Elements deeper in the nesting should get smaller weights, not larger ones. This is the reverse of a typical depth-weighted sum.

The key insight is that we need to know the maximum depth first before we can calculate any weights, because weight depends on maxDepth - depth + 1.

If we try to calculate weights during a single traversal, we won't know what the maximum depth is until we've seen everything.

This suggests we might need two passes: one to find the maximum depth, and another to calculate the weighted sum using that maximum depth.

Think about a company hierarchy where bonuses are given based on seniority. The CEO (top level) gets the highest bonus, managers (middle level) get medium bonuses, and individual contributors (deepest level) get the smallest bonuses.

But you can't calculate anyone's bonus until you know how many levels exist in the company! If there are 5 levels total, the CEO gets weight 5, but if there are 10 levels, the CEO gets weight 10. The maximum depth determines all weights.

Common Mistakes

Forgetting to find the maximum depth first in the two-pass approach - calculating weights without knowing maxDepth will give incorrect results

Off-by-one errors in weight calculation: the formula is maxDepth - depth + 1, not maxDepth - depth (depth 1 should get weight maxDepth, not maxDepth-1)

Not handling empty nested lists correctly - an empty list [] contributes nothing to the sum but still counts as a nesting level

In BFS approach, forgetting to carry forward the accumulated sum from previous levels - each level's contribution must be added multiple times based on how many levels remain

Confusing this problem with Nested List Weight Sum I - this problem uses REVERSE depth (shallower = heavier), while the original uses normal depth (deeper = heavier)

Optimal Solution

The optimal approach uses BFS (level-order traversal) with a clever insight: instead of weighting by maxDepth - depth + 1, we can process level by level and accumulate sums differently. At each level, add the current level sum to the total, but also carry forward all previous level sums. This way, elements at shallower depths naturally get added more times (higher weight) without needing to know the maximum depth in advance. This eliminates the need for two passes.

Visualization

from collections import deque
def depth_sum_inverse(nested_list):
    """
    Compute weighted sum where weight = maxDepth - depth + 1.
    Uses BFS with clever accumulation: add level sum to total at each level,
    and carry forward previous sums so shallower elements get added more times.
    """
    if not nested_list:
        return 0
    
    # Initialize queue with top-level elements
    queue = deque(nested_list)
    total_sum = 0
    level_sum = 0
    
    # BFS level-order traversal
    while queue:
        level_size = len(queue)
        
        # Process all elements at current level
        for _ in range(level_size):
            element = queue.popleft()
            
            # Check if element is integer or nested list
            if isinstance(element, int):
                level_sum += element
            else:
                # Add nested elements to queue for next level
                for nested in element:
                    queue.append(nested)
        
        # Add current level sum to total (carries forward to all deeper levels)
        total_sum += level_sum
    
    return total_sum

Start: Compute weighted sum with reverse depth

0 / 33

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n) We visit each of the n elements exactly once in a single BFS traversal, processing each element in constant time

Space Complexity: O(w) The queue stores at most w elements, where w is the maximum width of the nested structure (maximum number of elements at any single depth level)

What We've Learned

Two-pass depth calculation: When weights depend on maximum depth, use a first pass to find max depth before computing the weighted sum. This avoids complex recursion with return values and separates concerns cleanly - one traversal for structure analysis, another for computation.
Level-order BFS for nested structures: Use BFS with a queue to process nested lists level-by-level, which naturally groups elements by depth. This is more intuitive than DFS for problems requiring depth-aware processing, as each queue iteration represents exactly one depth level.
Reverse weight formula pattern: For reverse depth weighting, use weight = (maxDepth - currentDepth + 1) to ensure deepest elements get weight 1 and shallowest get maxDepth. The +1 adjustment is critical - without it, the deepest level would have weight 0.
Flattening vs. structure preservation: Recognize when to flatten nested structures into (value, depth) pairs versus maintaining the hierarchy. For weighted sums, extracting values with metadata during traversal simplifies the final calculation and avoids re-traversing the structure.
Queue-based depth tracking: Track depth by either storing (element, depth) tuples in the queue or processing all elements at current depth before moving to next level. The tuple approach is more flexible for irregular structures where you need per-element depth information.
Alternative single-pass optimization: Instead of computing reverse weights, use unweighted sum accumulation where you add each level's sum multiple times (once per remaining level). This eliminates the need to find max depth first, trading mathematical insight for a single traversal.

Test Your Understanding

Why is nested-list the right data structure for this problem?

nested-list provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late December, 2025

Mid-level

Late December, 2025

Mid-level

Exact same question

Mid December, 2025

Junior

Get Premium to View All 10+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 364. Nested List Weight Sum II

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact