Nested List Weight Sum solution and explanation
9 more videos on this problem
NESTED LIST WEIGHT SUM | LEETCODE # 339 | PYTHON BFS SOLUTIONCracking FAANG · 11:00 · 13K views
Amazon Coding Interview Question | Leetcode 339 | Nested List Weight SumWorkWithGoogler · 13:45 · 2K views
Leetcode 339 - Nested List Weight Sum (JAVA, Solution Explain!)LC Bear · 7:01 · 2K views
339. Nested List Weight Sum - English VersionSimple Code - 단순코드 · 6:41 · 1K views
339. Nested List Weight Sum - Week 2/5 Leetcode November ChallengeProgramming Live with Larry · 4:50 · 1K views
Leetcode 339 | Nested List Weight Sum | Meta/FacebookRoad To FAANG · 12:42 · 796 views
LEETCODE 339 NESTED LIST WEIGHT SUM PYTHON | DFS facebook interview questionSasa codes · 11:41 · 676 views
LeetCode Python 339 Nested List Weight SumNan Liu · 4:49 · 600 views
BFS Template : Nested List Weight Sum ( Leetcode-339 )Kumar Sanjeev · 8:47 · 505 views
LeetCode 339. Nested List Weight Sum | JSer - JavaScript & AlgorithmJSer · 10:15 · 426 views
The problem
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
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
# class NestedInteger:
# def __init__(self, value=None):
# """
# If value is not specified, initializes an empty list.
# Otherwise initializes a single integer equal to value.
# """
#
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def add(self, elem):
# """
# Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
# :rtype void
# """
#
# def setInteger(self, value):
# """
# Set this NestedInteger to hold a single integer equal to value.
# :rtype void
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """
class Solution:
def depthSum(self, nestedList: List[NestedInteger]) -> int:
def dfs(nestedList, depth):
depth_sum = 0
for item in nestedList:
if item.isInteger():
depth_sum += item.getInteger() * depth
else:
depth_sum += dfs(item.getList(), depth + 1)
return depth_sum
return dfs(nestedList, 1)/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* public interface NestedInteger {
* // Constructor initializes an empty nested list.
* public NestedInteger();
*
* // Constructor initializes a single integer.
* public NestedInteger(int value);
*
* // @return true if this NestedInteger holds a single integer, rather than a nested list.
* public boolean isInteger();
*
* // @return the single integer that this NestedInteger holds, if it holds a single integer
* // Return null if this NestedInteger holds a nested list
* public Integer getInteger();
*
* // Set this NestedInteger to hold a single integer.
* public void setInteger(int value);
*
* // Set this NestedInteger to hold a nested list and adds a nested integer to it.
* public void add(NestedInteger ni);
*
* // @return the nested list that this NestedInteger holds, if it holds a nested list
* // Return empty list if this NestedInteger holds a single integer
* public List<NestedInteger> getList();
* }
*/
class Solution {
public int depthSum(List<NestedInteger> nestedList) {
return dfs(nestedList, 1);
}
private int dfs(List<NestedInteger> nestedList, int depth) {
int depthSum = 0;
for (NestedInteger item : nestedList) {
if (item.isInteger()) {
depthSum += item.getInteger() * depth;
} else {
depthSum += dfs(item.getList(), depth + 1);
}
}
return depthSum;
}
}/**
* // This is the interface that allows for creating nested lists.
* // You should not implement it, or speculate about its implementation
* function NestedInteger() {
*
* Return true if this NestedInteger holds a single integer, rather than a nested list.
* @return {boolean}
* this.isInteger = function() {
* ...
* };
*
* Return the single integer that this NestedInteger holds, if it holds a single integer
* Return null if this NestedInteger holds a nested list
* @return {integer}
* this.getInteger = function() {
* ...
* };
*
* Set this NestedInteger to hold a single integer equal to value.
* @return {void}
* this.setInteger = function(value) {
* ...
* };
*
* Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
* @return {void}
* this.add = function(elem) {
* ...
* };
*
* Return the nested list that this NestedInteger holds, if it holds a nested list
* Return null if this NestedInteger holds a single integer
* @return {NestedInteger[]}
* this.getList = function() {
* ...
* };
* };
*/
/**
* @param {NestedInteger[]} nestedList
* @return {number}
*/
var depthSum = function (nestedList) {
const dfs = (nestedList, depth) => {
let depthSum = 0;
for (const item of nestedList) {
if (item.isInteger()) {
depthSum += item.getInteger() * depth;
} else {
depthSum += dfs(item.getList(), depth + 1);
}
}
return depthSum;
};
return dfs(nestedList, 1);
};Complexity analysis
| Approach | Time | Space | When 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. |
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.
