Problem of The Day: Nested List Weight Sum

Problem Statement

Intuition

My initial thought is that this problem involves traversing a nested structure where each integer has a depth associated with it. The deeper the integer is nested, the higher its contribution to the result due to multiplication by the depth.

Approach

I will use a depth-first search (DFS) approach to recursively traverse the nested list structure. For each integer found, its contribution will be multiplied by the depth at which it is located. If an element is a list, I will recursively dive deeper into that list, increasing the depth by 1.

Complexity

• Time complexity: The time complexity is \(O(n)\) where \(n\) is the total number of integers and lists in the nested structure. We visit each integer and nested list exactly once.

• Space complexity: The space complexity is \(O(d)\), where \(d\) is the maximum depth of the nested lists, which corresponds to the recursion depth of the DFS.

Code

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
#    def __init__(self, value=None):
#        """
#        If value is not specified, initializes an empty list.
#        Otherwise initializes a single integer equal to value.
#        """
#
#    def isInteger(self):
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        :rtype bool
#        """
#
#    def add(self, elem):
#        """
#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
#        :rtype void
#        """
#
#    def setInteger(self, value):
#        """
#        Set this NestedInteger to hold a single integer equal to value.
#        :rtype void
#        """
#
#    def getInteger(self):
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        :rtype int
#        """
#
#    def getList(self):
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        :rtype List[NestedInteger]
#        """

class Solution:
    def dfs(self, curr_item, depth):
        res = 0
        if isinstance(curr_item, int):
            res += (curr_item * depth)
        elif isinstance(curr_item, list):
            for item in curr_item:
                if item.isInteger():
                    res += (item.getInteger() * depth)
                else:
                    res += self.dfs(item.getList(), depth + 1)
        return res

    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        return self.dfs(nestedList, 1)

Editorial

Approach 1: Depth-first Search

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:

        def dfs(nested_list, depth):
            total = 0
            for nested in nested_list:
                if nested.isInteger():
                    total += nested.getInteger() * depth
                else:
                    total += dfs(nested.getList(), depth + 1)
            return total

        return dfs(nestedList, 1)

• time: O(n)
• space: O(n)

Approach 2: Breadth-first Search

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        queue = deque(nestedList)

        depth = 1
        total = 0

        while len(queue) > 0:
            for i in range(len(queue)):
                nested = queue.pop()
                if nested.isInteger():
                    total += nested.getInteger() * depth
                else:
                    queue.extendleft(nested.getList())
            depth += 1

        return total

• time: O(n)
• space: O(n)