Nested List Weight Sum II Solution in Python

Links to Other Languages

Code Solution


class Solution:
    def depthSumInverse(self, nestedList: list[NestedInteger]) -> int:
        ans = 0
        prevSum = 0
        q = collections.deque(nestedList)

        while q:
            for _ in range(len(q)):
                ni = q.popleft()
                if ni.isInteger():
                    prevSum += ni.getInteger()
                else:
                    for nextNi in ni.getList():
                        q.append(nextNi)
            ans += prevSum

        return ans

Problem Description

Welcome to the world of nested lists, where the only thing more confusing than your last relationship is trying to calculate the weighted sum of integers at different depths! The problem, aptly named Nested List Weight Sum II, asks you to sum up integers in a nested list, but with a twist: the deeper the integer, the more weight it carries.

Imagine you’re at a family reunion, and your relatives are all sitting in a giant nested circle. The deeper you go into the circle (or the more layers of relatives you have to navigate), the more annoying they become. So, if you want to calculate how much you dread each layer, you need to weigh their annoyance by how deep they are in the circle.

In simpler terms, if you have a list like [1, [4, [6]]], the sum would be 1 + 4*2 + 6*3 = 27. Because, let’s face it, the deeper you go, the more you wish you had stayed home!

Approach

The provided solution uses a breadth-first search (BFS) approach to traverse the nested list. It maintains a queue to process each element, checking if it’s an integer or another list. If it’s an integer, it adds its value to a cumulative sum that increases with each level of depth. The final answer is the total weighted sum of all integers, where the weight is determined by their depth in the nested structure.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N), where N is the total number of integers in the nested list. Each integer is processed exactly once.
Space Complexity	O(D), where D is the maximum depth of the nested list. This is due to the space used by the queue to hold elements at each level.

Real-World Example

Think of a company hierarchy where the CEO is at the top (depth 1) and the interns are at the bottom (depth 3). If you were to calculate the total “influence” of each employee based on their position, you’d want to weigh the CEO’s influence more heavily than that of the interns. This mirrors the Nested List Weight Sum II problem, where deeper integers contribute more to the final sum.