LeetCode 364. Nested List Weight Sum II

relevent: LeetCode 339. Nested List Weight Sum

Problem Clarification

NestedInteger interface: isInteger(), getInteger(), getList()

Input: [1, [4, 6]], List[NestedInteger]
Output: sum of all integers weighted by their depth

Depth definition:

  1. Nested List Weight Sum: depth increasing from root to leaf, i.e. top down
    • One 1 at depth 1, one 4 at depth 2, one 6 at depth 3; 1x1+4x2+6x3=27
  2. Nested List Weight Sum II: depth increasing from leaf to root, i.e. bottom up
    • One 1 at depth 3, one 4 at depth 2, one 6 at depth 1; 1x3+4x2+6x1=17

Analysis

  1. Nested List Weight Sum
    • Recursion (DFS): Use a helper function helperSum(nestedList, depth). For each element nestedInteger in the list, add nestedInteger.getInteger() * depth if it’s an integer, otherwise recursively call helperSum(nestedInteger.getList(), depth + 1) and add it’s return.
    • Iteration (BFS): Sum all integers in the current depth. When encountered a nested list, store it for the next-round processing where depth is incremented by 1.
  2. Nested List Weight Sum II
    • Store separate sums for each depth when using BFS, then calculate the weighted overall sum together.
    • Calculate the top down weighted sum depthSum as before and the “flat” sum unweighted, then calculate the difference (maxDepth + 1) * unweighted - depthSum
    • Use two variables unweighted sum and weighted sum, for each iteration, update unweighted when encounted an integer, then update weighted += unweighted after the iteration finishes. This is equivalent to: add all encountered integers one time more when found a deeper depth.

Code

  1. Nested List Weight Sum
    • DFS 
      class Solution:
 def depthSum(self, nestedList: List[NestedInteger]) -> int:
   def helperSum(nestedList, depth):
       res = 0
       for item in nestedList:
           if item.isInteger():
               res += item.getInteger() * depth
           else:
               res += helperSum(item.getList(), depth + 1)
       return res
   return helperSum(nestedList, 1)
    • BFS 
      class Solution:
 def depthSum(self, nestedList: List[NestedInteger]) -> int:
   queue = collections.deque(nestedList)
   depth = 1
   ans = 0
   while queue:
       currentLen = len(queue)
       for i in range(currentLen):
           nestedInteger = queue.popleft()
           if nestedInteger.isInteger():
               ans += nestedInteger.getInteger() * depth
           else:
               queue.extend(nestedInteger.getList())
       depth += 1
   return ans
  2. Nested List Weight Sum II 
    class Solution:
 def depthSumInverse(self, nestedList: List[NestedInteger]) -> int:
     queue = collections.deque(nestedList)
     unweighted, weighted = 0, 0
     while queue:
         currLen = len(queue)
         for _ in range(currLen):
             nestedInteger = queue.popleft()
             if nestedInteger.isInteger():
                 unweighted += nestedInteger.getInteger()
             else:
                 queue.extend(nestedInteger.getList())
         weighted += unweighted
     return weighted