Week 3 Bonus - Nested List Weight Sum

#leetcode #python #challenge

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

Link to code

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

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.

DEV Community