## DEV Community is a community of 618,434 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Week 3 Bonus - Nested List Weight Sum

Ruairí O'Brien ・2 min read

## 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):
else:
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)

``````

## 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.