Week 3 Bonus - Nested List Weight Sum
Tags: leetcode, python, challenge
Published: 2021-01-19 19:36:43

## 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:__

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/12hp5vc0ebbn5ofksun1.png)

```
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:__

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/gvnflr3t7jejf5ngjrc8.png)

```
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

[Link to code](https://github.com/ruarfff/leetcode-jan-2021)

```python
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

[Link to code](https://github.com/ruarfff/leetcode-jan-2021)

```python
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

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/e1vjss8102sgurgnkz6l.png)

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/ycokdcx9v96gr474fdtb.png)


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