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.

Description Solution Video 9:19

364. Nested List Weight Sum II

Medium66.8% acceptance3 companiesPremium elsewhere, free here

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.

Asked at 3 companies

Google Meta

Topics

9:19

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

364. Nested List Weight Sum II

Asked at 3 companies

Topics

Similar problems