The Problem
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. 1*2 + 1*2 + 2*1 + 1*2 + 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. 1*1 + 4*2 + 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.
Tests
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, [6]]], 27),
([0], 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
Solution
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)
Analysis
Commentary
This solution didn't perform very well relatively. It does run in O(n) with 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.
Top comments (0)