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],[,2],1] has each integer's value set to its depth.
Return the sum of each integer in nestedList multiplied by its depth.
Input: nestedList = [[1,1],2,[1,1]] Output: 10 Explanation: Four 1's at depth 2, one 2 at depth 1. 1*2 + 1*2 + 2*1 + 1*2 + 1*2 = 10.
Input: nestedList = [1,[4,]] Output: 27 Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.
Input: nestedList =  Output: 0
1 <= nestedList.length <= 50
- The values of the integers in the nested list is in the range
- The maximum depth of any integer is less than or equal to
import pytest from typing import List from .Week3Bonus_NestedListWeightSum import Solution from .util import NestedInteger s = Solution() @pytest.mark.parametrize( "num_list,expected", [ ([[1, 1], 2, [1, 1]], 10), ([1, [4, ]], 27), (, 0), ], ) def test_depth_sum(num_list, expected): x = build_nested_list(num_list) for n in x: print(n) print(n.isInteger()) assert s.depthSum(x) == expected def build_nested_list(num_list) -> List[NestedInteger]: nestedList =  for n in num_list: if isinstance(n, int): nestedList.append(NestedInteger(n)) else: nestedList.append(list_to_nested_int(n)) return nestedList def list_to_nested_int(nums): ni = NestedInteger() for n in nums: if isinstance(n, int): ni.add(NestedInteger(n)) else: ni.add(list_to_nested_int(n)) return ni
from typing import List from .util import NestedInteger class Solution: def depthSumWithDepth(self, nestedList: List[NestedInteger], depth: int): sum = 0 # Iterate over the list. If we hit an int, add it to the sum multiplying by depth for n in nestedList: if n.isInteger(): sum += n.getInteger() * depth else: # Recursively sump up all the sub lists incrementing the depth as needed sum += self.depthSumWithDepth(n.getList(), depth + 1) return sum def depthSum(self, nestedList: List[NestedInteger]) -> int: # Start at depth 1 return self.depthSumWithDepth(nestedList, 1)
This solution didn't perform very well relatively. It does run in
O(n) space. I am not sure we can get much better than that in terms of big O but there's probably some optimisation I could have done. Recursion is generally not a good idea in python I think since it will add each function call to the call stack. I am happy enough with the solution here for now since it's easy to understand but an easy one to improve on.