Nested List Weight Sum

The given problem asks to calculate the sum of all integers in the nested list, each multiplied by its depth.

To solve this, we’ll write a recursive function that will traverse the given nested list and multiply each integer by its depth, adding the products together. The base case will be when an integer is found, at which point it is multiplied by its depth and returned.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        def dfs(nestedInteger: NestedInteger, depth: int) -> int:
            if nestedInteger.isInteger():
                return nestedInteger.getInteger() * depth
            else:
                sum_ = 0
                for elem in nestedInteger.getList():
                    sum_ += dfs(elem, depth + 1)
                return sum_

        total_sum = 0
        for item in nestedList:
            total_sum += dfs(item, 1)

        return total_sum

Explanation

  1. dfs Function: A depth-first search function that takes a NestedInteger object and the current depth. If the object is an integer, it returns the product of the integer and the depth. If it’s a list, it recursively calls itself for each element in the list, incrementing the depth by 1.

  2. Iterating through nestedList: We iterate through the given nestedList, and for each NestedInteger, we call the dfs function with depth 1.

  3. Returning the Sum: The sum of all the products is returned.

Key Takeaways

  • The function makes use of recursion to handle the nested structure of the input.
  • The time complexity of this code is (O(N)), where (N) is the total number of integers in the nested list, and the space complexity is (O(D)), where (D) is the maximum depth of the nested list.

System Analyst Hat

Understand the problem

  1. Define the interface Input: NestedInteger[] nested_list Output: Integer

  2. Define the term

    • What is a nested list?
      • What is a nested integer
      • Nested list is an array of nested integers
      • Is an array of NestedInteger objects

    Terminology

    • What is depth?
    • Can you see the examples and define depth in simple terms?
    • Pattern recognitions skill and ability to ask questions
    • In example 1, the pair of ones is nested inside the array whereas 2 is by itself in the array as a single element.
    • Depth means how deep the elements are nested inside the array

  3. What should we extract from this problem statement?

    • What is implicit? How can we derive the implicit info from the statement? When we look at the input
      • Input can have nesting that is multiple levels
    • What is explicit?

Programmer’s Hat

  1. [[1,1],2,[1,1]] 2 * 1 + 2 * 2 + 2 * 2 = 10

    1 + 42 + 63 1 * depth of 1 + 4 * depth of 4 + 6 * depth of 6

    Analyze the concrete cases Generalize it to a valid expression

  2. How to calculate the depth?

    [NestedInteger, NestedInteger, NestedInteger] get_list

    We can use is_integer to check if the element is an integer. depth = 1 Iterate that list and check if it is an integer

    What to calculate the depth for 2 and 3.

    • NestedInteger is_integer ? depth = 2
    • NestedInteger false depth = 3

  3. DFS comes handy

    • Recursive Approach

  4. Solution Outline

    • We have to process each element in the list?
    • Our unit of work is to process each element in the list
      • Do we need to calculate depth for each element.
      • We need to keep track of the depth for every recursive call
      • Everytime we call the recursive call,
      • Two conditions If it is just an integer
    • Base Cases Empty array - return 0 Single integer - Example: [2] => Return the integer

  5. Recurrence Relation

    weight_sum(input) = weighted(input[1..-1] ) + input[0] * 1 if input[0] is an integer weighted(input[1..-1] ) + input[0] * depth?
    if input[0] is a list

    1 + 42 + 63 = output 1 * depth of 1 + 4 * depth of 4 + 6 * depth of 6

    [[1,1],2,[1,1]]

    (1+1) * 2 + 2 * 1 + (1+1) * 2 = 10

    1 * 2 + 1 * 2 + 2 * 1 + 2 * 1 + 1 * 2

    summation * depth +

Time: O( ) Space: O( )

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
#
#class NestedInteger
#    def is_integer()
#        """
#        Return true if this NestedInteger holds a single integer, rather than a nested list.
#        @return {Boolean}
#        """
#
#    def get_integer()
#        """
#        Return the single integer that this NestedInteger holds, if it holds a single integer
#        Return nil if this NestedInteger holds a nested list
#        @return {Integer}
#        """
#
#    def set_integer(value)
#        """
#        Set this NestedInteger to hold a single integer equal to value.
#        @return {Void}
#        """
#
#    def add(elem)
#        """
#        Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
#        @return {Void}
#        """
#
#    def get_list()
#        """
#        Return the nested list that this NestedInteger holds, if it holds a nested list
#        Return nil if this NestedInteger holds a single integer
#        @return {NestedInteger[]}
#        """
# @param {NestedInteger[]} nested_list
# @return {Integer}

def wrapper(nested_list, depth)
    for i in (0..nested_list.size-1)
       if nested_list[i].is_integer
           @output += nested_list[i].get_integer * depth
       else
           wrapper(nested_list[i].get_list(), depth+1)
       end 
    end   
    return @output
end

def depth_sum(nested_list)
    depth = 1
    @output = 0
    wrapper(nested_list, depth)
    @output
end