364. Nested List Weight Sum II

Description

Given a nested list of integers, each element is either an integer or a nested list. The depth of an integer is the number of lists it's nested within. The weight of an integer is maxDepth - depth + 1, where maxDepth is the maximum depth of any integer in the nested list. The problem asks to calculate the sum of each integer multiplied by its weight.

Solution: Depth-First Search (DFS)

This solution uses a Depth-First Search (DFS) approach to traverse the nested list. It leverages the observation that the final weighted sum can be calculated efficiently using the total sum of integers (s) and the weighted sum of integers (ws), where the weight is the depth.

The algorithm works as follows:

1. Initialization: Initialize maxDepth, s (sum of integers), and ws (weighted sum of integers) to 0.

2. DFS Function (dfs): This recursive function takes a NestedInteger element x and its current depth d as input.

   • It updates maxDepth to track the maximum depth encountered.
   • If x is an integer, it adds x to s and adds x * d to ws.
   • If x is a nested list, it recursively calls dfs on each element of the list, incrementing the depth d.

3. Main Loop: Iterate through the input nestedList. For each element, call dfs with an initial depth of 1.

4. Result Calculation: After traversing the entire list, the weighted sum is calculated as (maxDepth + 1) * s - ws.

Code Implementation (Python)

class Solution:
    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
        maxDepth = s = ws = 0
 
        def dfs(x, d):
            nonlocal maxDepth, s, ws
            maxDepth = max(maxDepth, d)
            if x.isInteger():
                s += x.getInteger()
                ws += x.getInteger() * d
            else:
                for y in x.getList():
                    dfs(y, d + 1)
 
        for x in nestedList:
            dfs(x, 1)
        return (maxDepth + 1) * s - ws
 

Time and Space Complexity Analysis

• Time Complexity: O(N), where N is the total number of integers in the nested list. The DFS algorithm visits each integer exactly once.
• Space Complexity: O(D), where D is the maximum depth of the nested list. The space complexity is dominated by the recursion stack used during the DFS traversal. In the worst case, the depth of the recursion stack can be as large as the maximum depth of the nested list. If the list is very flat (small depth), the space complexity approaches O(1).

Other Language Implementations

The same algorithm can be implemented in other languages like Java, C++, JavaScript, and Go with minor syntactic changes. The core logic remains consistent across all languages. (See the provided solution for examples in these languages).