Practice/LinkedIn/Leetcode 364. Nested List Weight Sum II

Leetcode 364. Nested List Weight Sum II

CodingMust

Problem

You are given a nested list of integers where each element can either be an integer or another list (which itself can contain integers or more nested lists). Your task is to calculate a weighted sum where the weight of each integer is inversely proportional to its depth.

Specifically, the weight for an integer at a given depth is calculated as: weight = maxDepth - depth + 1, where:

• maxDepth is the maximum nesting level in the entire structure
• depth is the current nesting level (starting at 1 for the outermost level)

This means integers at deeper levels receive smaller weights, while integers closer to the surface receive larger weights.

Requirements

1. Calculate the maximum depth of nesting in the entire structure
2. For each integer, determine its depth level
3. Apply the inverse weight formula: weight = maxDepth - depth + 1
4. Return the sum of all integers multiplied by their respective weights

Constraints

• The nested list contains at least one integer
• All integers are in the range [-1000, 1000]
• Maximum nesting depth is 50
• Total number of integers across all nesting levels ≤ 10,000
• Time complexity should be O(n) where n is the total number of elements
• Space complexity should be O(d) where d is the maximum depth

Examples

Example 1:

` Input: [[1,1],2,[1,1]] Output: 8 Explanation:

• Maximum depth is 2
• Four 1's at depth 2: each contributes 1 × (2-2+1) = 1 × 1 = 1
• One 2 at depth 1: contributes 2 × (2-1+1) = 2 × 2 = 4
• Total: 1+1+1+1+4 = 8 `

Example 2:

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

• Maximum depth is 3
• 1 at depth 1: 1 × (3-1+1) = 1 × 3 = 3
• 4 at depth 2: 4 × (3-2+1) = 4 × 2 = 8
• 6 at depth 3: 6 × (3-3+1) = 6 × 1 = 6
• Total: 3+8+6 = 17 `

Example 3:

` Input: [1,2,3,4] Output: 10 Explanation:

• Maximum depth is 1 (flat list)
• All elements at depth 1: each has weight (1-1+1) = 1
• Total: 1×1 + 2×1 + 3×1 + 4×1 = 10 `