Leetcode 364. Nested List Weight Sum II

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?

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.

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

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.

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.

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

• 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.