Nested List Weight Sum
Nested List Weight Sum is a medium recursion & backtracking problem solved with the basic recursion pattern.
The best approach, optimal (bfs level by level), runs in O(N) time and O(N) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from recursive dfs up.
Problem
You are given a nested list of integers nestedList. Every element is either an integer or another list, whose elements can again be integers or lists.
The depth of an integer is the number of lists that contain it: integers directly in nestedList have depth 1, integers inside one sub-list have depth 2, and so on. Return the sum of every integer multiplied by its depth.
You may only inspect the structure through the NestedInteger interface: isInteger() tells you whether an element holds a single integer, getInteger() returns that integer, and getList() returns the element’s list.
Examples
Example 1
- Input
nestedList = [3, [4, [-1]], 2]- Output
10- Why
- 3 and 2 are at depth 1, 4 at depth 2 and -1 at depth 3: 3·1 + 4·2 + (-1)·3 + 2·1 = 10.
Example 2
- Input
nestedList = [[1, 1], 7]- Output
11- Why
- The two 1s sit at depth 2 and 7 at depth 1: 1·2 + 1·2 + 7·1 = 11.
Example 3
- Input
nestedList = [[[[6]]]]- Output
24- Why
- The only integer is wrapped in four lists, so it is at depth 4: 6·4 = 24.
Constraints
1 <= nestedList.length <= 50- Every integer is in the range
[-100, 100]. - The maximum depth of any integer is at most
50. - Lists may be empty.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Recursive DFS | O(N) | O(D) |
| Optimal (BFS level by level) | O(N) | O(N) |
1Recursive DFS
O(N)N is the total number of integers and lists; each one is visited once.O(D)The recursion stack is as deep as the nesting depth D.Walk the structure recursively, carrying the depth. Integers add value × depth; sub-lists are explored with depth + 1.
- Call dfs(nestedList, 1).
- In dfs(list, d): for each element, add value · d if it is an integer, otherwise add dfs(element's list, d + 1).
- Return the total.
class Solution {
public int depthSum(List<NestedInteger> nestedList) {
return dfs(nestedList, 1);
}
private int dfs(List<NestedInteger> list, int depth) {
int total = 0;
for (NestedInteger ni : list) {
if (ni.isInteger()) total += ni.getInteger() * depth;
else total += dfs(ni.getList(), depth + 1);
}
return total;
}
}class Solution:
def depthSum(self, nestedList: List["NestedInteger"]) -> int:
def dfs(lst: List["NestedInteger"], depth: int) -> int:
total = 0
for ni in lst:
if ni.isInteger():
total += ni.getInteger() * depth
else:
total += dfs(ni.getList(), depth + 1)
return total
return dfs(nestedList, 1)class Solution {
int dfs(const vector<NestedInteger>& list, int depth) {
int total = 0;
for (const NestedInteger& ni : list) {
if (ni.isInteger()) total += ni.getInteger() * depth;
else total += dfs(ni.getList(), depth + 1);
}
return total;
}
public:
int depthSum(vector<NestedInteger>& nestedList) {
return dfs(nestedList, 1);
}
};function depthSum(nestedList) {
function dfs(list, depth) {
let total = 0;
for (const ni of list) {
if (ni.isInteger()) total += ni.getInteger() * depth;
else total += dfs(ni.getList(), depth + 1);
}
return total;
}
return dfs(nestedList, 1);
}2Optimal (BFS level by level)
O(N)Every integer and list enters and leaves the queue once.O(N)The queue can hold a whole level, which is O(N) in the worst case.Put the top-level elements in a queue and process it one level at a time. Every element taken out during level d sits at depth d: integers add value × d, lists push their elements for level d + 1. No recursion is needed.
- queue = all elements of nestedList, depth = 1, total = 0.
- While the queue is not empty, process exactly the current queue size of elements.
- Integer: total += value · depth. List: append all of its elements to the queue.
- After the level, depth++.
class Solution {
public int depthSum(List<NestedInteger> nestedList) {
Deque<NestedInteger> queue = new ArrayDeque<>(nestedList);
int depth = 1, total = 0;
while (!queue.isEmpty()) {
for (int k = queue.size(); k > 0; k--) {
NestedInteger ni = queue.poll();
if (ni.isInteger()) total += ni.getInteger() * depth;
else queue.addAll(ni.getList());
}
depth++;
}
return total;
}
}class Solution:
def depthSum(self, nestedList: List["NestedInteger"]) -> int:
level = list(nestedList)
depth = 1
total = 0
while level:
nxt = []
for ni in level:
if ni.isInteger():
total += ni.getInteger() * depth
else:
nxt.extend(ni.getList())
level = nxt
depth += 1
return totalclass Solution {
public:
int depthSum(vector<NestedInteger>& nestedList) {
queue<const NestedInteger*> q;
for (const NestedInteger& ni : nestedList) q.push(&ni);
int depth = 1, total = 0;
while (!q.empty()) {
for (int k = q.size(); k > 0; k--) {
const NestedInteger* ni = q.front();
q.pop();
if (ni->isInteger()) {
total += ni->getInteger() * depth;
} else {
for (const NestedInteger& child : ni->getList()) q.push(&child);
}
}
depth++;
}
return total;
}
};function depthSum(nestedList) {
let level = [...nestedList];
let depth = 1, total = 0;
while (level.length > 0) {
const next = [];
for (const ni of level) {
if (ni.isInteger()) total += ni.getInteger() * depth;
else next.push(...ni.getList());
}
level = next;
depth++;
}
return total;
}Edge cases to test
- Empty inner lists contribute nothing
- Negative integers, which can make the total zero or negative
- Deep nesting where a single integer gets a large weight
- A flat list: every weight is 1, so the answer is the plain sum
Hints
Hint 1
Pass the current depth down as you walk the structure. An integer contributes value × depth.
Hint 2
Recursion does it naturally: depthSum(list, d) adds value·d for integers and depthSum(sub-list, d + 1) for lists.
Hint 3
Without recursion, a queue processed level by level gives each element its depth for free: the level number is the depth.
FAQ
What is the best time complexity for Nested List Weight Sum?
Optimal (BFS level by level) runs in O(N) time and O(N) extra space. Every integer and list enters and leaves the queue once.
Which pattern does Nested List Weight Sum use?
It is a recursion & backtracking problem that uses the basic recursion pattern. Other problems with the same pattern: Factorial of a number, Fibonacci Number, Binary Tree Inorder Traversal (Recursive).
Is there a brute force solution for Nested List Weight Sum?
Yes. Recursive DFS takes O(N) time and O(D) space. Walk the structure recursively, carrying the depth.
Which edge cases should I test for Nested List Weight Sum?
Empty inner lists contribute nothing; Negative integers, which can make the total zero or negative; Deep nesting where a single integer gets a large weight; A flat list: every weight is 1, so the answer is the plain sum.