We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Nested List Weight Sum II

Number: 364

Difficulty: Medium

Paid? Yes

Companies: LinkedIn, Google

Problem Description

Given a nested list of integers, each integer’s weight is determined by how deep it is inside the list. However, the weight is calculated as "maxDepth - (current depth) + 1" where maxDepth is the maximum depth among all integers in the list. The goal is to compute the sum of each integer multiplied by its weight.

Key Insights

  • First determine the maximum depth (maxDepth) of any integer in the nested list.
  • Use a traversal (DFS or BFS) to calculate the depth of every integer.
  • In a second pass, calculate the sum by multiplying each integer by (maxDepth - current depth + 1).
  • Two passes enable conversion of a bottom-up weighted sum that essentially reverses the normal depth weight.

Space and Time Complexity

Time Complexity: O(n) where n is the total number of nested elements (each element is processed twice). Space Complexity: O(d) where d is the maximum depth due to recursion/stack usage.

Solution

The solution uses a Depth-First Search (DFS) approach with two passes. In the first pass, we traverse the nested list and record the maximum depth encountered. In the second pass, we re-traverse the list, and for each integer encountered, we compute its weighted contribution by multiplying it by (maxDepth - current depth + 1) and summing these contributions. This two-pass method is more straightforward than calculating the weight on the fly because the weight of an integer depends on the overall maximum depth which is only known after a full traversal. The key data structure used here is recursion (or an explicit stack) to handle the nested structure of the list.

Code Solutions

# Define the NestedInteger class interface if needed.
# Here, for simplicity, assume nestedList is represented as a list of either integers or lists.
def depth_helper(nested_list, depth):
    # Recursively calculate the maximum depth of the nested list.
    max_depth = depth
    for element in nested_list:
        if isinstance(element, list):
            max_depth = max(max_depth, depth_helper(element, depth + 1))
    return max_depth

def weighted_sum_helper(nested_list, depth, max_depth):
    total = 0
    for element in nested_list:
        if isinstance(element, list):
            total += weighted_sum_helper(element, depth + 1, max_depth)
        else:
            # Calculate weight as (max_depth - depth + 1)
            total += element * (max_depth - depth + 1)
    return total

def nestedListWeightSumII(nestedList):
    # First pass: find the maximum depth
    max_depth = depth_helper(nestedList, 1)
    # Second pass: calculate the weighted sum
    return weighted_sum_helper(nestedList, 1, max_depth)

# Example usage:
# For input: [[1,1],2,[1,1]]
print(nestedListWeightSumII([[1,1], 2, [1,1]]))  # Expected output: 8
← Back to All Questions