DFS/BFS

Question 1

”””

339. Nested List Weight Sum
     Solved
     Medium
     Topics
     Companies

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer’s value set to its depth.

Return the sum of each integer in nestedList multiplied by its depth.

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: 10
Explanation: Four 1’s at depth 2, one 2 at depth 1. 12 + 12 + 21 + 12 + 1*2 = 10.

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 11 + 42 + 6*3 = 27.

Example 3:

Input: nestedList = [0]
Output: 0

Constraints:

1 <= nestedList.length <= 50
The values of the integers in the nested list is in the range [-100, 100].
The maximum depth of any integer is less than or equal to 50.

NL Interface to use.

# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger(object):
#    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]
#        """

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

Answer 1

DFS, always pass list type to the method. Get the list from the nestedList object. The root entry is a list of nestedList objects.

10 Minutes Target.

class Solution(object):
    def depthSum(self, nestedList):
        """
        :type nestedList: List[NestedInteger]
        :rtype: int
        """
        
        def rec_depth_sum(nL, depth):
            ret_sum = 0
            for element in nL:
                if element.isInteger():
                    ret_sum += element.getInteger()*depth
                else:
                    ret_sum += rec_depth_sum(element.getList(), depth+1)
            return ret_sum
        
        return rec_depth_sum(nestedList, 1)

BFS,
Use current queue length to go over the elements at that level.
if you find a nestedList extend the queue with its elements, else multiply the integer with current level and add to sum
increment level and continue

from collections import deque
class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        # bfs
        q = deque(nestedList)
        depth = 1
        total = 0
        while q:
            qln = len(q)
            for _ in range(qln):
                element = q.popleft()
                if element.isInteger():
                    total += element.getInteger() * depth
                else:
                    q.extend(element.getList())
            depth += 1
        return total

10 Minutes

O(n), O(n)

Question 2

364. Nested List Weight Sum II

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists.

The depth of an integer is the number of lists that it is inside of. For example, the nested list [1,[2,2],[[3],2],1] has each integer’s value set to its depth. Let maxDepth be the maximum depth of any integer.

The weight of an integer is maxDepth - (the depth of the integer) + 1.

Return the sum of each integer in nestedList multiplied by its weight.

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

Answer 2

from collections import deque
class Solution:
    def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
        q = deque(nestedList)
        total_sum = 0
        weighted_sum = 0
        depth = 1
        max_depth = 1
        while q:
            qlen = len(q)
            level_sum = 0
            for _ in range(qlen):
                item = q.popleft()
                if item.isInteger():
                    level_sum += item.getInteger()
                else:
                    q.extend(item.getList())
            weighted_sum += level_sum * depth
            total_sum += level_sum
            max_depth = depth
            depth+=1
        return (total_sum * (max_depth + 1)) - weighted_sum 

O(n), O(n)