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

Number: 339

Difficulty: Medium

Paid? Yes

Companies: Meta, LinkedIn, Amazon, TikTok

Problem Description

Given a nested list of integers where each element is either an integer or another list, compute the sum of all integers weighted by their depth. The weight is defined by the depth at which the integer is found (e.g., an integer at depth 2 is multiplied by 2). For example, in the nested list [1,[4,[6]]], the integer 1 is at depth 1, 4 is at depth 2, and 6 is at depth 3, so the weighted sum is 11 + 42 + 6*3 = 27.

Key Insights

  • Use recursion (or an iterative BFS approach) to process each element and track its current depth.
  • For each integer, multiply it by its current depth and add it to the result.
  • For each sublist, recursively process it with the depth increased by one.
  • The problem leverages either a depth-first search (DFS) with recursion or a breadth-first search (BFS) with a queue.

Space and Time Complexity

Time Complexity: O(n), where n is the total number of integers and list elements since each is visited once. Space Complexity: O(n) in the worst-case scenario due to the recursion call stack (for deeply nested structures) or the queue size in a BFS approach.

Solution

We can solve the problem using a DFS recursive strategy. The idea is to traverse the nested list while maintaining the current depth. If the element is an integer, multiply it by the depth; if it is a list, recursively traverse it with depth+1. This approach ensures that each integer is processed with the correct weight according to its depth.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java.

# Python solution using DFS recursion

def depthSum(nestedList):
    # Helper function that takes list and current depth
    def dfs(lst, depth):
        total = 0  # Initialize sum for current list
        for element in lst:
            # If element is a list, do recursive DFS call with increased depth
            if isinstance(element, list):
                total += dfs(element, depth + 1)
            else:
                # Element is an integer: add integer multiplied by current depth
                total += element * depth
        return total
    
    # Start recursion at depth 1
    return dfs(nestedList, 1)

# Example usage:
print(depthSum([[1,1], 2, [1,1]]))  # Output: 10
print(depthSum([1, [4, [6]]]))        # Output: 27
← Back to All Questions