Leetcode 364. Nested List Weight Sum II (Python)

Related Topic

Depth-First-Search.

Description

Given a nested list of integers, return the sum of all integers in the list weighted by their depth.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Different from the previous question where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight.

Sample I/O

Example 1

Input: [[1,1],2,[1,1]]
Output: 8 
Explanation: Four 1's at depth 1, one 2 at depth 2.

Example 2

Input: [1,[4,[6]]]
Output: 17 
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17.

Methodology

This question can be solved by Depth First Search and it is similar with question 339. Nested List Weight Sum. This time is digit elements will be higher level than list elements.

Weight sum is level depth times sum. We first iterate all elements from the list, if the element is digit, we sum up. If element is list, we merge all list element into one list. After iterate all elements, we use dfs, to recursively find the sum of the new list, the level sum is previous sum plus the new list sum.

Code

def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
        def dfs(nestedList, list_sum):
            temp_list = []
            for elem in nestedList:
                if elem.isInteger():
                    list_sum += elem.getInteger()
                else:
                    temp_list += elem.getList()
            if len(temp_list) != 0:
                list_sum+=dfs(temp_list, list_sum)
            return list_sum
        return dfs(nestedList, 0)

BigO

We traversal all elements of nested list so total time complexity is O(n) where n is the number of the elements