Problem statement

https://leetcode.com/problems/nested-list-weight-sum-ii/

Solution

Here, before we can really evaluate desired sum, we need to find the maximum depth of our list. We can use Problem 0339, but use negative weights: starting from $-1$ and decreasing them as we go deeper. Then we evaluate sum of all numbers (without weights), multiply it by (maximum depth + 1) and add negative weighted sum.

Complexity

Time complexity is still $O(n)$, however we need to passes over data.

Code

class Solution:
    def depthSumInverse(self, nestedList):
        self.maxDepth = 0
        Sum1 = sum([self.getSum(e) for e in nestedList])
        Sum2 = sum([self.getSumW(e,-1) for e in nestedList])
        return Sum1*(1-self.maxDepth) + Sum2
        
    def getSumW(self, elem, depth):
        self.maxDepth = min(self.maxDepth, depth)
        if elem.isInteger():
            return elem.getInteger() * depth 
        else:
            return sum([self.getSumW(e, depth - 1) for e in elem.getList()])
            
    def getSum(self, elem):
        if elem.isInteger():
            return elem.getInteger() 
        else:
            return sum([self.getSum(e) for e in elem.getList()])

Remark

There is another solution, using BFS and queue. Is it possible to do it in one pass though?