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 eitherintorlist. - 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 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.
- Initialize a running total (
total_sum) for this specific branch of recursion. - Iterate through each item in
nestedList. - Check if the item is an integer:
- If yes, add
(item_value * depth)tototal_sum.
- If yes, add
- 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 tototal_sum.
- Recursively call this function with that sublist and
- Return
total_sumonce 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: , where 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: for recursion stack space, where is the maximum depth of nesting. Given constraints (), 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=1initially. - 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;
totalremains unchanged from that branch. - Negative values: The arithmetic operation
(item * current_depth)correctly handles negative inputs (e.g.,-5 * 3 = -15).