Leetcode 339. Nested List Weight Sum

Problem

You are given a structure that contains integers and nested lists. Each element can be either an integer or a list that may contain more integers or lists, creating arbitrary levels of nesting.

Calculate the weighted sum where each integer contributes to the total based on its nesting depth. An integer at depth 1 (top level) contributes its value multiplied by 1, an integer at depth 2 contributes its value multiplied by 2, and so on.

For example, in the structure [1, [2, 3]], the integer 1 is at depth 1 and contributes 1×1=1, while integers 2 and 3 are at depth 2 and contribute 2×2=4 and 3×2=6 respectively, for a total of 11.

Requirements

1. Process each element in the nested structure recursively or iteratively
2. Track the current depth as you traverse deeper into nested lists
3. For each integer found, multiply it by its depth and add to the running total
4. Handle arbitrarily deep nesting levels
5. Return the final weighted sum as an integer

Constraints

• The nested structure contains between 1 and 100 elements at the top level
• Maximum nesting depth is 50
• Each integer value is between -100 and 100
• Empty lists may appear in the structure (contribute 0 to sum)
• Time complexity should be O(n) where n is the total number of integers
• Space complexity should be O(d) where d is the maximum depth (for recursion stack or queue)

Examples

Example 1:

Input: [[1,1],2,[1,1]] Output: 10 Explanation: Four 1's at depth 2 contribute 4*2=8, and one 2 at depth 1 contributes 2*1=2. Total: 8+2=10

Example 2:

` Input: [1,[4,[6]]] Output: 27 Explanation:

• 1 is at depth 1: 1*1 = 1
• 4 is at depth 2: 4*2 = 8
• 6 is at depth 3: 6*3 = 18 Total: 1+8+18 = 27 `

Example 3:

Input: [1,2,3,4] Output: 10 Explanation: All integers are at depth 1: (1+2+3+4)*1 = 10

Hint 1: Traversal Strategy Consider using either a recursive depth-first approach or an iterative breadth-first approach with a queue. Both allow you to track the current depth as you explore the structure.

Hint 2: Depth Tracking Pass the current depth as a parameter in your recursive calls, starting with depth=1 at the top level. Increment the depth by 1 when you recurse into a nested list.

Hint 3: Type Checking In Python, use isinstance(element, int) to check if an element is an integer. If it's not an integer, treat it as a list and recurse into it with an incremented depth.

Full Solution ` def depthSum(nestedList): """ Calculate weighted sum where each integer is multiplied by its depth. Uses recursive depth-first traversal.

Time Complexity: O(n) where n is total number of integers
Space Complexity: O(d) where d is maximum depth (recursion stack)
"""
def helper(nested, depth):
    total = 0
    for element in nested:
        if isinstance(element, int):
            # If it's an integer, add value * depth
            total += element * depth
        else:
            # If it's a list, recurse with increased depth
            total += helper(element, depth + 1)
    return total

return helper(nestedList, 1)

`

Explanation:

The solution uses a recursive helper function that traverses the nested structure while tracking the current depth:

1. Base Case: When we encounter an integer, we multiply it by the current depth and add to the sum
2. Recursive Case: When we encounter a list, we recurse into it with depth incremented by 1
3. Accumulation: We accumulate the sum from all branches and return the total

Alternative Iterative Approach:

` def depthSum(nestedList): """ Iterative BFS approach using a queue with (element, depth) pairs. """ from collections import deque

total = 0
queue = deque()

# Initialize queue with top-level elements at depth 1
for element in nestedList:
    queue.append((element, 1))

while queue:
    element, depth = queue.popleft()
    
    if isinstance(element, int):
        total += element * depth
    else:
        # Add nested elements with incremented depth
        for nested_element in element:
            queue.append((nested_element, depth + 1))

return total

`

Complexity Analysis:

• Time Complexity: O(n) where n is the total number of integers in the structure. We visit each element exactly once.
• Space Complexity: O(d) where d is the maximum depth. In the recursive approach, this is the recursion stack depth. In the iterative approach, it's the maximum number of elements at any depth level in the queue.

Both approaches are equally valid. The recursive solution is more concise and intuitive, while the iterative solution avoids potential stack overflow issues with extremely deep nesting.