339. Nested List Weight Sum

Problem Statement

link: LeetCode.cn LeetCode

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer’s value set to its depth.

Return the sum of each integer in nestedList multiplied by its depth.

Example:

Input: nestedList = [[1,1],2,[1,1]] Output: 10

Input: nestedList = [1,[4,[6]]] Output: 27

Input: nestedList = [0] Output: 0

Constraints:

1 <= nestedList.length <= 50 The values of the integers in the nested list is in the range [-100, 100]. The maximum depth of any integer is less than or equal to 50.

Solution Approach

The solution uses depth-first search (DFS) to recursively calculate the sum of integers in the nested list, multiplying each integer by its depth

Algorithm

1. Depth Calculation: For each integer encountered in the nested list, multiply its value by its current depth, which represents the number of nested lists it is inside.
2. Recursive Traversal: If an element in the list is another nested list, recursively call the function, increasing the depth by 1, to continue processing deeper levels.
3. Sum Accumulation: Accumulate the weighted sums from both integers and deeper nested lists to obtain the total sum for the entire structure.

Complexity

time complexity: O(N)where N is the total number of integers and lists in the nested structure space complexity: O(D)where D is the maximum depth of the nested list.

Implement

    class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        def dfs(nestedList, depth):
            total = 0
            for nested in nestedList:
                if nested.isInteger():
                    total += nested.getInteger() * depth
                else:
                    total += dfs(nested.getList(), depth + 1)
            return total
        return dfs(nestedList, 1)
                

    
    

Twitter  facebook  Email