Skip to main content
Talentd

Nested List Weight Sum II - Solution & Explanation

MediumPremiumFree on FleetCodeStackDepth-First SearchBreadth-First Search18 min readAsked at: Meta, Google, LinkedIn
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. Let maxDepth be the maximum depth of any integer.

The weight of an integer is maxDepth - (the depth of the integer) + 1.

Return the sum of each integer in nestedList multiplied by its weight.

 

Example 1:

Input: nestedList = [[1,1],2,[1,1]]
Output: 8
Explanation: Four 1's with a weight of 1, one 2 with a weight of 2.
1*1 + 1*1 + 2*2 + 1*1 + 1*1 = 8

Example 2:

Input: nestedList = [1,[4,[6]]]
Output: 17
Explanation: One 1 at depth 3, one 4 at depth 2, and one 6 at depth 1.
1*3 + 4*2 + 6*1 = 17

 

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.
  • There are no empty lists.

Approach Overview

Problem Overview: You receive a nested list of integers where each element can either be a single integer or another list. The weight of each integer is determined by its depth from the bottom of the structure. Integers at the deepest level have weight 1, and the weight increases as you move toward the root. The task is to compute the total weighted sum.

Approach 1: Two-Pass DFS (O(n) time, O(d) space)

This method uses Depth-First Search to first determine the maximum depth of the nested structure. A recursive DFS walks through each element, increasing the depth when entering sublists. Once the maximum depth is known, run another DFS traversal and multiply each integer by (maxDepth - currentDepth + 1). Every element is visited twice, but the overall work remains linear. Space complexity is O(d) due to the recursion stack where d is the nesting depth.

Approach 2: BFS Level Accumulation (O(n) time, O(w) space)

A more elegant solution uses Breadth-First Search to process the structure level by level. Maintain two variables: unweighted (sum of all integers seen so far) and weighted (final result). During each level traversal, add integers to unweighted. After finishing the level, add unweighted to weighted. Because shallow integers persist across multiple levels, they effectively gain higher weights. This avoids computing maximum depth entirely while still visiting each element exactly once.

The BFS approach typically uses a queue to process lists iteratively. Each time you encounter a nested list, push its elements into the queue for the next level. This pattern is closely related to level-order traversal problems and sometimes appears with a Stack or queue depending on the implementation style.

Recommended for interviews: The BFS accumulation approach is usually the strongest answer. It solves the inverse-weight requirement without explicitly computing depth and keeps the runtime O(n) with clean logic. The two-pass DFS solution still demonstrates solid recursion and tree traversal skills, so mentioning it briefly shows broader understanding.

Solution

Let's assume the integers are a_1, a_2, cdots, a_n, their depths are d_1, d_2, cdots, d_n, the maximum depth is maxDepth, then the answer is:

$ a_1 times maxDepth - a_1 times d_1 + a_1 + a_2 times maxDepth - a_2 times d_2 + a_2 + cdots + a_n times maxDepth - a_n times d_n + a_n

which is:

(maxDepth + 1) times (a_1 + a_2 + cdots + a_n) - (a_1 times d_1 + a_2 times d_2 + cdots + a_n times d_n)

If we denote the sum of all integers as s, and the sum of each integer multiplied by its depth as ws, then the answer is:

(maxDepth + 1) times s - ws

Therefore, we design a function dfs(x, d), which starts searching from x with depth d. The execution process of dfs(x, d) is as follows:

  • We first update maxDepth = max(maxDepth, d);
  • If x is an integer, then we update s = s + x, ws = ws + x times d;
  • Otherwise, we recursively traverse each element y of x, and call dfs(y, d + 1).

We traverse the entire list, for each element x, we call dfs(x, 1), and finally return (maxDepth + 1) times s - ws.

The time complexity is O(n), and the space complexity is O(n). Where n$ is the number of integers.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Two-Pass DFSO(n)O(d)When recursion is preferred and computing maximum depth first makes the logic clearer
BFS Level AccumulationO(n)O(w)Best general solution; processes levels iteratively without computing depth

Video Solution

Leetcode 364 - Nested List Weight Sum II (JAVA Solution Explained!) • LC Bear • 3,814 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Nested List Weight Sum II easy or hard?
Nested List Weight Sum II is generally rated Medium difficulty. The challenge comes from recognizing that weights depend on distance from the bottom rather than the top. Once that insight is clear, a BFS accumulation or two-pass DFS approach solves the problem efficiently.
Nested List Weight Sum II Python/Java solution
The problem can be implemented in Python, Java, C++, Go, TypeScript, and JavaScript using DFS or BFS traversal. Python solutions typically use recursion for DFS or a deque for BFS. Java implementations often use a Queue for level traversal while accumulating weighted sums.
How to solve Nested List Weight Sum II in O(n)?
Traverse the nested list using BFS and maintain two variables: an unweighted running sum and a weighted result. At each level, add integers to the unweighted sum and then add that value to the weighted total. Because earlier integers are counted multiple times across levels, they receive larger weights automatically. Every element is processed once, giving O(n) time complexity.
What is the best approach for Nested List Weight Sum II?
The BFS level accumulation approach is usually considered the best solution. It processes the nested structure level by level while maintaining running sums of integers seen so far. Each level contributes the accumulated value again, which naturally applies inverse depth weights. The algorithm runs in O(n) time and avoids explicitly calculating the maximum depth.
Is Nested List Weight Sum II asked at Google/Amazon/Meta?
Nested list traversal and weighted sum variations frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. The problem tests recursive thinking, BFS traversal, and handling hierarchical data structures. Interviewers often look for the optimized O(n) solution.
What data structure is used in Nested List Weight Sum II?
Common implementations use recursion with Depth-First Search or a queue for Breadth-First Search. DFS relies on the call stack to explore nested lists, while BFS uses a queue to process elements level by level. Both approaches handle hierarchical list structures efficiently.
What is the time complexity of Nested List Weight Sum II?
The optimal solutions run in O(n) time where n is the total number of integers and lists in the nested structure. Both DFS and BFS approaches visit every element exactly once. The space complexity depends on recursion depth for DFS or queue width for BFS.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Array Nesting

Next

Nested List Weight Sum