364. Nested List Weight Sum II

MediumStackDepth-First SearchBreadth-First Search
Leetcode Link

Problem Description

This LeetCode problem involves calculating the weighted sum of integers within a nested list, where the weight depends on the depth of each integer in the nested structure. The nested list is a list that can contain integers as well as other nested lists to any depth. The depth of an integer is defined by how many lists are above it. For example, if we have the nested list [1,[2,2],[[3],2],1], the integer 1 at the start and end is at depth 1, the integers 2 in the first inner list are at depth 2, the integer 3 is at depth 3 since it is inside two lists, and so on.

To determine the weighted sum, we need to calculate the 'weight' of each integer, which is defined as the maximum depth of any integer in the entire nested structure minus the depth of that integer, plus 1. The task then is to calculate this weighted sum of all integers in the nested list.

Intuition

To arrive at the solution for this problem, we need to follow a two-step approach.

First, we determine the maximum depth of the nested list. This requires us to traverse the nested lists and keep track of the depth as we go. We can do this using a max_depth helper function that recursively goes through each element, increasing the depth when it encounters a nested list and comparing the current depth with the maximum depth found so far.

Second, we calculate the weighted sum of all integers within the nested list structure using this maximum depth. We can create a dfs (depth-first search) helper function that recursively traverses the nested list structure. When the function encounters an integer, it multiplies it by the weight, which is the maximum depth minus the current depth of the integer plus one. If it encounters another nested list, it calls itself with the new depth that's one less than the current maximum depth. By summing up the results of these multiplications and recursive calls, we get the weighted sum of all integers in the nested list.

Learn more about Stack, Depth-First Search and Breadth-First Search patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

In a binary min heap, the maximum element can be found in:

Solution Approach

The implementation of the solution utilizes a recursive depth-first search (DFS) approach. This is a common pattern for traversing tree or graph-like data structures, which is similar to the nested list structure we're dealing with here. The Solution class provides two functions: max_depth and dfs, which work together to solve the problem.

max_depth is a helper function that calculates the deepest level of nesting in the given nestedList. It initializes a variable depth to 1, to represent the depth of the outermost list, and iterates through each item in the current list. For each item that is not an integer (i.e., another nested list), it makes a recursive call to get the maximum depth of that list and compares it with the current depth to keep track of the highest value. The function returns the maximum depth it finds.

The dfs function is the core of the depth-first search algorithm. It operates recursively, computing the sum of the integers in the nestedList, weighted by their depth. For each item in nestedList, it checks whether the item is an integer or a nested list. If it's an integer, the function calculates the weight of the integer using the formula maxDepth - (the depth of the integer) + 1 and adds this weighted integer to the depth_sum. If the item is a nested list, the dfs function is called recursively, with max_depth decreased by 1 to account for the increased nesting. This ensures that integers nested deeper inside the structure are weighted appropriately. The computed depth_sum for each recursive call is then added up to form the total sum.

Finally, the depthSumInverse function of the Solution class uses these helper functions to calculate and return the final weighted sum. It first calls max_depth to find the maximum depth of the list, and then calls dfs, passing the nestedList and the maximum depth as arguments.

Altogether, this is an efficient and elegant solution that makes clever use of recursion to traverse and process the nested list structure.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's use a small nested list example to illustrate the solution approach: [2, [1, [3]], 4].

  1. Calculating Maximum Depth:

    • We start by determining the maximum depth of the nested structure with the max_depth function.
    • The list [2, [1, [3]], 4] starts with depth 1 at the outermost level.
    • Element '2' is an integer at depth 1.
    • Element '[1, [3]]' is a nested list. We apply max_depth recursively.
      • Inside this list, '1' is an integer at depth 2.
      • The element '[3]' is a nested list. Again, we apply max_depth recursively.
        • The integer '3' is at depth 3.
    • Element '4' is an integer at depth 1.
    • The maximum depth of these elements is 3. This is the maxDepth.

  2. Calculating Weighted Sum via DFS:

    • Next, we use the dfs function to calculate the weighted sum.
    • For each element, if it's an integer, we calculate its weighted value by maxDepth - currentDepth + 1.
    • Start with element '2', which is an integer at depth 1. Its weight is 3 - 1 + 1 = 3. So it contributes 2 * 3 = 6 to the sum.
    • Move to element '[1, [3]]', which is a nested list. We apply dfs recursively.
      • The integer '1' at depth 2 has a weight of 3 - 2 + 1 = 2. It contributes 1 * 2 = 2.
      • For the nested list '[3]', apply dfs recursively.
        • The integer '3' at depth 3 has a weight of 3 - 3 + 1 = 1. It contributes 3 * 1 = 3.
    • Finally, the integer '4' at depth 1 has a weight of 3 - 1 + 1 = 3. It contributes 4 * 3 = 12.
    • The sum of all weighted integers is 6 + 2 + 3 + 12 = 23.

  3. Combining the Functions (The depthSumInverse Function):

    • The depthSumInverse function combines the use of both max_depth and dfs.
    • First, it finds the maximum depth with max_depth(nestedList) which gives us maxDepth = 3.
    • Then it calculates the weighted sum with dfs(nestedList, maxDepth), which gives us the weighted sum 23.
    • It returns 23 as the final result.

To summarize, this approach efficiently processes each integer with its appropriate weight, determined by its depth in the nested list structure, to calculate the requested weighted sum.

Solution Implementation

1# Using the interface provided, we define a solution class with methods to calculate the inverse depth sum for a nested integer list.
2class Solution:
3    def depthSumInverse(self, nested_list):
4        # This helper function computes the maximum depth of the nested integer list.
5        def max_depth(nested_list):
6            depth = 1  # Start with depth 1 since there's at least one level of nesting.
7            for item in nested_list:
8                if not item.isInteger():
9                    # For any nested list, calculate the depth recursively and update the maximum depth accordingly.
10                    current_depth = max_depth(item.getList()) + 1
11                    depth = max(depth, current_depth)
12            return depth  # Return the maximum depth found.
13
14        # This is a helper function that computes the sum of integers in the nested list, each multiplied by its "inverse" depth.
15        def dfs(nested_list, level_multiplier):
16            depth_sum = 0  # Initialize depth sum.
17            for item in nested_list:
18                if item.isInteger():
19                    # If the item is an integer, multiply it by the level_multiplier.
20                    depth_sum += item.getInteger() * level_multiplier
21                else:
22                    # If the item is a list, make a recursive call and decrease the level_multiplier.
23                    depth_sum += dfs(item.getList(), level_multiplier - 1)
24            return depth_sum  # Return the computed depth sum for this level.
25
26        max_depth_value = max_depth(nested_list)  # Calculate the maximum depth of the input nested list.
27        return dfs(nested_list, max_depth_value)  # Call the dfs function starting with the maximum depth as the level multiplier.
28
1class Solution {
2    // Calculate the inverse depth sum of the given nest integer list.
3    public int depthSumInverse(List<NestedInteger> nestedList) {
4        // First, find the maximum depth of the nested list.
5        int maxDepth = findMaxDepth(nestedList);
6        // Then, calculate the depth sum with depth weights in inverse order.
7        return calculateDepthSumInverse(nestedList, maxDepth);
8    }
9
10    // A helper method to determine the maximum depth of the nested integer list.
11    private int findMaxDepth(List<NestedInteger> nestedList) {
12        int depth = 1; // Initialize the minimum depth.
13        for (NestedInteger item : nestedList) {
14            // If the current item is a list, calculate its depth.
15            if (!item.isInteger()) {
16                // Recursively find the max depth for the current list + 1 for the current level.
17                depth = Math.max(depth, 1 + findMaxDepth(item.getList()));
18            }
19            // If it's an integer, it does not contribute to increasing the depth.
20        }
21        return depth; // Return the maximum depth found.
22    }
23
24    // A helper method to recursively calculate the weighted sum of integers at each depth.
25    private int calculateDepthSumInverse(List<NestedInteger> nestedList, int weight) {
26        int depthSum = 0; // Initialize sum for the current level.
27        for (NestedInteger item : nestedList) {
28            // If the current item is an integer, multiply it by its depth weight.
29            if (item.isInteger()) {
30                depthSum += item.getInteger() * weight;
31            } else {
32                // If the item is a list, recursively calculate the sum of its elements
33                // with the weight reduced by 1 since we're going one level deeper.
34                depthSum += calculateDepthSumInverse(item.getList(), weight - 1);
35            }
36        }
37        return depthSum; // Return the total sum for this level.
38    }
39}
40
1#include <vector>
2#include <algorithm>
3
4// Forward declaration of the NestedInteger class interface. Assuming it is predefined.
5class NestedInteger {
6public:
7    // Returns true if this NestedInteger holds a single integer, rather than a nested list.
8    bool isInteger() const;
9
10    // Returns the single integer that this NestedInteger holds, if it holds a single integer.
11    // The result is undefined if this NestedInteger holds a nested list.
12    int getInteger() const;
13
14    // Returns the nested list that this NestedInteger holds, if it holds a nested list.
15    // The result is undefined if this NestedInteger holds a single integer.
16    const std::vector<NestedInteger> &getList() const;
17};
18
19/**
20 * Calculates the maximum depth of nested lists within a list of NestedInteger
21 * @param nested_list - The list of NestedInteger to evaluate.
22 * @return The maximum depth found.
23 */
24int getMaxDepth(const std::vector<NestedInteger>& nested_list) {
25    int depth = 1;
26    for (const auto& item : nested_list) {
27        if (!item.isInteger()) {
28            // Recursively find the depth of this nested list and compare it with the current depth
29            depth = std::max(depth, 1 + getMaxDepth(item.getList()));
30        }
31    }
32    return depth;
33}
34
35/**
36 * Recursively calculates the inverse depth sum of a NestedInteger list
37 * @param nested_list - The current level of NestedInteger
38 * @param depth - The depth to multiply the integers with
39 * @return The calculated depth inverse sum.
40 */
41int calculateDepthInverseSum(const std::vector<NestedInteger>& nested_list, int depth) {
42    int depth_sum = 0;
43    for (const auto& item : nested_list) {
44        if (item.isInteger()) {
45            // Multiply the integer by its depth
46            depth_sum += item.getInteger() * depth;
47        } else {
48            // Recursively calculate the depth sum of nested lists, one level deeper
49            depth_sum += calculateDepthInverseSum(item.getList(), depth - 1);
50        }
51    }
52    return depth_sum;
53}
54
55/**
56 * Calculates the sum of all integers in a NestedInteger list weighted by their depth,
57 * with the integers deepest in the list weighted the most.
58 * @param nested_list - The list of NestedInteger to sum up
59 * @return The weighted sum where deeper integers carry more weight.
60 */
61int depthSumInverse(const std::vector<NestedInteger>& nested_list) {
62    // Find the maximum depth to start the inverse weighting
63    int max_depth = getMaxDepth(nested_list);
64    // Calculate the inverse depth sum starting from the maximum depth
65    return calculateDepthInverseSum(nested_list, max_depth);
66}
67
1// This TypeScript function calculates the inverse depth sum of a NestedInteger list.
2
3/**
4 * Calculates the maximum depth of nested lists within a list of NestedInteger
5 * @param {NestedInteger[]} nestedList - The list of NestedInteger to evaluate.
6 * @return {number} - The maximum depth found.
7 */
8function getMaxDepth(nestedList: NestedInteger[]): number {
9    let depth: number = 1;
10    for (const item of nestedList) {
11        if (!item.isInteger()) {
12            // Recursively find the depth of this nested list and compare it with the current depth
13            depth = Math.max(depth, 1 + getMaxDepth(item.getList()));
14        }
15    }
16    return depth;
17}
18
19/**
20 * Recursively calculates the inverse depth sum of a NestedInteger list
21 * @param {NestedInteger[]} nestedList - The current level of NestedInteger
22 * @param {number} depth - The depth to multiply the integers with
23 * @return {number} - The calculated depth inverse sum.
24 */
25function calculateDepthInverseSum(nestedList: NestedInteger[], depth: number): number {
26    let depthSum: number = 0;
27    for (const item of nestedList) {
28        if (item.isInteger()) {
29            // Multiply the integer by its depth
30            depthSum += item.getInteger() * depth;
31        } else {
32            // Recursively calculate the depth sum of nested lists, one level deeper
33            depthSum += calculateDepthInverseSum(item.getList(), depth - 1);
34        }
35    }
36    return depthSum;
37}
38
39/**
40 * Calculates the sum of all integers in a NestedInteger list weighted by their depth,
41 * with the integers deepest in the list weighted the most.
42 * @param {NestedInteger[]} nestedList - The list of NestedInteger to sum up
43 * @return {number} - The weighted sum where deeper integers carry more weight.
44 */
45function depthSumInverse(nestedList: NestedInteger[]): number {
46    // Find the maximum depth to start the inverse weighting
47    const depth: number = getMaxDepth(nestedList);
48    // Calculate the inverse depth sum starting from the maximum depth
49    return calculateDepthInverseSum(nestedList, depth);
50}
51
Not Sure What to Study? Take the 2-min Quiz๏ผš

How many times is a tree node visited in a depth first search?

Time and Space Complexity

Time Complexity

The time complexity of the provided code is primarily dependent on two functions: max_depth and dfs.

  • The max_depth function computes the maximum depth of the nested list. In the worst case, it visits each element in the nested list and calculates the depth by making a recursive call for each list it encounters. This results in a time complexity of O(N), where N is the total number of elements and nested lists within the outermost list because it has to potentially go through all elements at different levels of nesting to calculate the maximum depth.

  • The dfs (depth-first search) function visits each element in the nested list once and for each integer it finds, it performs an operation that takes O(1) time. Where the function encounters nested lists, it makes a recursive call, decrementing the max_depth by one. The time complexity of dfs is also O(N), with the same definition of N as above.

Therefore, the overall time complexity of the code is O(N), combining the time it takes to calculate the maximum depth and then to perform the depth-first search.

Space Complexity

The space complexity is taken up by the recursion call stack in both max_depth and dfs functions.

  • The max_depth function will occupy space on the call stack up to the maximum depth of D, where D is the maximum level of nesting, resulting in a space complexity of O(D).

  • The dfs function also uses recursion, and in the worst-case scenario, it will have a stack depth of D as well, giving us another O(D).

Since these functions are not called recursively within each otherโ€”but instead, one after the otherโ€”the overall space complexity does not multiply, and the space complexity remains O(D).

In conclusion, the time complexity of the code is O(N) and the space complexity is O(D).

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Stack Intro

Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

BFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ