Skip to main content
Talentd

Nested List Weight Sum - Solution & Explanation

MediumPremiumFree on FleetCodeDepth-First SearchBreadth-First Search7 min readAsked at: Amazon, Meta, Oracle +3
Practice this problem

Problem Statement

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.

Approach Overview

Problem Overview: You receive a nested list where each element is either an integer or another list. Each integer contributes to the final sum multiplied by its depth in the structure. The task is to traverse the nested structure and compute the weighted sum of all integers.

Approach 1: Depth-First Search (Recursive Traversal) (Time: O(n), Space: O(d))

The most common solution uses recursion with Depth-First Search. Iterate through each element in the current list. If the element is an integer, add value × depth to the result. If it is another list, recursively process that list with depth + 1. Every nested element is visited exactly once, so the time complexity is O(n), where n is the total number of integers and lists. The recursion stack stores at most the current nesting depth, giving O(d) space complexity.

This approach mirrors the structure of the input. The recursive call naturally tracks the depth, which avoids additional data structures. When implementing the logic, the key operation is checking whether an element is an integer or a list and branching accordingly. This method is concise and typically the fastest to write during interviews.

Approach 2: Breadth-First Search (Level Order Traversal) (Time: O(n), Space: O(w))

An alternative uses Breadth-First Search. Instead of diving deep into the structure, process the nested lists level by level using a queue. Start by pushing the initial list into the queue with depth 1. For each item removed from the queue, multiply integers by the current depth and push nested lists back into the queue with depth + 1. Every element is still processed once, keeping time complexity at O(n).

The queue may temporarily store many elements from the same level, so the space complexity becomes O(w), where w is the maximum width of the nested structure. This method is useful when you want explicit control over level processing, similar to level-order traversal in trees.

Both strategies treat the nested list as a hierarchical structure similar to a tree. DFS relies on recursion to track depth automatically, while BFS tracks depth through queue entries.

Recommended for interviews: The recursive DFS solution is what most interviewers expect. It directly reflects the problem’s hierarchical nature and produces clean code with minimal bookkeeping. BFS demonstrates the same understanding using an iterative structure. Showing DFS first proves you understand recursion and nested traversal, which is commonly evaluated in problems involving DFS and nested data structures.

Solution

Code

PythonJavaJavaScript

Python

Java

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Depth-First Search (Recursive)O(n)O(d)Best general solution. Clean recursive implementation when nested depth is manageable.
Breadth-First Search (Queue)O(n)O(w)Useful when processing the structure level by level or avoiding recursion.

Video Solution

NESTED LIST WEIGHT SUM | LEETCODE # 339 | PYTHON BFS SOLUTION • Cracking FAANG • 13,841 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Nested List Weight Sum easy or hard?
Nested List Weight Sum is generally classified as a medium difficulty problem. The main challenge is recognizing that the nested list behaves like a tree and applying DFS or BFS traversal while tracking depth.
Nested List Weight Sum Python/Java solution
Python, Java, and JavaScript solutions usually implement recursive DFS. Each call iterates through the current nested list, multiplies integers by the current depth, and recursively processes sublists with depth + 1. The algorithm runs in O(n) time.
How to solve Nested List Weight Sum in O(n)?
Traverse the nested structure once using DFS or BFS. For DFS, recursively process each list while tracking the current depth and add value × depth for every integer encountered. Since each element is visited once, the overall runtime stays O(n).
What is the best approach for Nested List Weight Sum?
The depth-first search (DFS) recursive approach is typically considered the best solution. It traverses the nested list structure and multiplies each integer by its depth during recursion. This method runs in O(n) time and uses O(d) space for the recursion stack, where d is the maximum depth of nesting.
Is Nested List Weight Sum asked at Google/Amazon/Meta?
Nested structure traversal problems like Nested List Weight Sum frequently appear in interviews at companies such as Google, Amazon, and Meta. They test recursion, tree-like traversal, and the ability to handle hierarchical data structures.
What data structure is used in Nested List Weight Sum?
The problem uses a nested list abstraction similar to a tree. DFS solutions rely on recursion (implicit stack), while BFS solutions use a queue to process elements level by level along with their depth.
What is the time complexity of Nested List Weight Sum?
The time complexity is O(n) because every integer and nested list element is visited exactly once during traversal. Both DFS and BFS implementations process each element a single time while computing the weighted contribution.

Ready to solve this problem?

Practice Nested List Weight Sum with our built-in code editor and test cases.

Practice on FleetCode
Previous

Array Nesting

Next

Employee Importance