Domain 2MediumCORE

Nested List Weight Sum

We are given a nested structure where elements can be either integers or lists containing further integers/lists. The goal is to calculate a weighted sum: every integer contributes its value multiplied by the number of list containers that enclose it (its depth).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Depth-first Search#Breadth-first Search

339. Nested List Weight Sum

Model: qwen3.5:9b
Topics: Depth-first Search,Breadth-first Search
FAANG asked: 1
Acceptance rate: 76.8%


Problem Breakdown

We are given a nested structure where elements can be either integers or lists containing further integers/lists. The goal is to calculate a weighted sum: every integer contributes its value multiplied by the number of list containers that enclose it (its depth).

Key inputs and outputs:

  • Input: A mixed-type collection (nestedList) representing the root container. Elements are either int or list.
  • Output: An integer summing (value * depth) for all integers found within the structure.
  • Implicit Constraints:
    • Depth starts at 1 (based on Example 2: top-level elements have weight factor of 1).
    • Negative values are allowed, so we must handle arithmetic correctly without assuming positive-only inputs.
    • The nesting depth is bounded by 50, which suggests recursion will not hit stack overflow limits in Python.

Intuition

The core challenge here is tracking the “depth” of each integer as we traverse the structure.

If I try to do this iteratively without a helper function or queue state, it becomes messy because I need to know how many times an element was wrapped before processing its value. A brute-force approach might involve trying to count wrappers for every number individually, which would be O(N2)O(N^2) if we traverse up the tree repeatedly—inefficient and unnecessary given Python’s recursion limits are high enough here.

The key insight is that depth increases naturally as we move deeper into a list. This suggests Depth-First Search (DFS). We can pass the current depth down through recursive calls. When we encounter an integer, we multiply it by the passed depth. If we hit another list, we increment the depth and recurse again. This keeps state local to each call frame without needing a complex queue or global counter.

Approach

I will implement a helper function (or method) that takes the current nested structure and an integer representing the current depth level.

  1. Initialize a running total (total_sum) for this specific branch of recursion.
  2. Iterate through each item in nestedList.
  3. Check if the item is an integer:
    • If yes, add (item_value * depth) to total_sum.
  4. If it’s a list (not an int):
    • Recursively call this function with that sublist and depth + 1. Add the result of that recursive call to total_sum.
  5. Return total_sum once all items in the current level are processed.

This approach ensures every integer is visited exactly once, accumulating its weighted value as it bubbles up from deeper levels or gets added at shallower ones.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the total number of integers and lists in the structure (the size of nestedList). We visit every element exactly once to check its type and process it.
  • Space Complexity: O(D)O(D) for recursion stack space, where DD is the maximum depth of nesting. Given constraints (D≤50D \le 50), this is negligible compared to input storage but technically linear with respect to max depth in a general case (e.g., [[[...]]]).

Solution

def depthSum(nestedList):
    """
    Calculates the weighted sum of integers based on their nesting depth.
    
    Args:
        nestedList (list): A list containing either ints or sub-lists.
        
    Returns:
        int: The calculated weight sum.
    """
    def dfs(current_list, current_depth):
        total = 0
        for item in current_list:
            if isinstance(item, int):
                # If integer, add value * depth to accumulator
                total += item * current_depth
            else:
                # If list, recurse with incremented depth and accumulate result
                total += dfs(item, current_depth + 1)
        return total

    return dfs(nestedList, 1)

Edge Cases Handled

  • Top-level integers: The code handles elements at the root level correctly by passing depth=1 initially.
  • Deeply nested lists: Since recursion depth is limited to 50 (per constraints), Python’s default stack limit (~1000) prevents overflow, and logic naturally increments depth for each nesting layer.
  • Empty sub-lists: If a list inside the structure contains no integers or only empty containers, the loop simply skips them without error; total remains unchanged from that branch.
  • Negative values: The arithmetic operation (item * current_depth) correctly handles negative inputs (e.g., -5 * 3 = -15).