Practice/Meta/Leetcode 339. Nested List Weight Sum

Leetcode 339. Nested List Weight Sum

CodingMust

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