Nested List Weight Sum II
Nested List Weight Sum II is a medium recursion & backtracking problem solved with the basic recursion pattern.
The best approach, optimal (one-pass bfs with running sum), runs in O(N) time and O(N) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from two-pass dfs up.
Problem
You are given a nested list of integers nestedList. Every element is either an integer or another non-empty 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). Let maxDepth be the largest depth of any integer. The weight of an integer is maxDepth - depth + 1, so the deepest integers have weight 1 and the outermost ones have the largest weight. Return the sum of every integer multiplied by its weight.
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
22- Why
- maxDepth is 3. Weights: 3 and 2 (depth 1) get 3, 4 (depth 2) gets 2, -1 (depth 3) gets 1: 9 + 8 - 1 + 6 = 22.
Example 2
- Input
nestedList = [[1, 1], 7]- Output
16- Why
- maxDepth is 2. The 1s at depth 2 have weight 1 and the 7 at depth 1 has weight 2: 1 + 1 + 14 = 16.
Example 3
- Input
nestedList = [[5, [2]], [[1]]]- Output
13- Why
- maxDepth is 3. 5 is at depth 2 (weight 2); 2 and 1 are at depth 3 (weight 1): 10 + 2 + 1 = 13.
Constraints
1 <= nestedList.length <= 50- Every integer is in the range
[-100, 100]. - The maximum depth of any integer is at most
50. - No list is empty, so every list contains at least one integer somewhere inside it.
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 |
|---|---|---|
| Two-pass DFS | O(N) | O(D) |
| Optimal (one-pass BFS with running sum) | O(N) | O(N) |
1Two-pass DFS
O(N)Each of the two passes visits every integer and list once; N counts both.O(D)The recursion depth equals the nesting depth D.First walk the structure recursively to find the deepest level that holds an integer. Then walk it again, giving each integer at depth d the weight maxDepth - d + 1.
- maxDepth(list, d): the largest d at which an integer appears (recurse into sub-lists with d + 1).
- weighted(list, d, D): add value · (D - d + 1) for integers, recurse into sub-lists with d + 1.
- Return weighted(nestedList, 1, maxDepth(nestedList, 1)).
class Solution {
public int depthSumInverse(List<NestedInteger> nestedList) {
int maxDepth = maxDepth(nestedList, 1);
return weighted(nestedList, 1, maxDepth);
}
private int maxDepth(List<NestedInteger> list, int depth) {
int best = 0;
for (NestedInteger ni : list) {
if (ni.isInteger()) best = Math.max(best, depth);
else best = Math.max(best, maxDepth(ni.getList(), depth + 1));
}
return best;
}
private int weighted(List<NestedInteger> list, int depth, int maxDepth) {
int total = 0;
for (NestedInteger ni : list) {
if (ni.isInteger()) total += ni.getInteger() * (maxDepth - depth + 1);
else total += weighted(ni.getList(), depth + 1, maxDepth);
}
return total;
}
}class Solution:
def depthSumInverse(self, nestedList: List["NestedInteger"]) -> int:
def max_depth(lst: List["NestedInteger"], depth: int) -> int:
best = 0
for ni in lst:
if ni.isInteger():
best = max(best, depth)
else:
best = max(best, max_depth(ni.getList(), depth + 1))
return best
def weighted(lst: List["NestedInteger"], depth: int, top: int) -> int:
total = 0
for ni in lst:
if ni.isInteger():
total += ni.getInteger() * (top - depth + 1)
else:
total += weighted(ni.getList(), depth + 1, top)
return total
return weighted(nestedList, 1, max_depth(nestedList, 1))class Solution {
int maxDepth(const vector<NestedInteger>& list, int depth) {
int best = 0;
for (const NestedInteger& ni : list) {
if (ni.isInteger()) best = max(best, depth);
else best = max(best, maxDepth(ni.getList(), depth + 1));
}
return best;
}
int weighted(const vector<NestedInteger>& list, int depth, int top) {
int total = 0;
for (const NestedInteger& ni : list) {
if (ni.isInteger()) total += ni.getInteger() * (top - depth + 1);
else total += weighted(ni.getList(), depth + 1, top);
}
return total;
}
public:
int depthSumInverse(vector<NestedInteger>& nestedList) {
return weighted(nestedList, 1, maxDepth(nestedList, 1));
}
};function depthSumInverse(nestedList) {
function maxDepth(list, depth) {
let best = 0;
for (const ni of list) {
if (ni.isInteger()) best = Math.max(best, depth);
else best = Math.max(best, maxDepth(ni.getList(), depth + 1));
}
return best;
}
function weighted(list, depth, top) {
let total = 0;
for (const ni of list) {
if (ni.isInteger()) total += ni.getInteger() * (top - depth + 1);
else total += weighted(ni.getList(), depth + 1, top);
}
return total;
}
return weighted(nestedList, 1, maxDepth(nestedList, 1));
}2Optimal (one-pass BFS with running sum)
O(N)Each integer and list is handled exactly once.O(N)One level of elements is held at a time, which can be O(N).Process the structure level by level. Keep running, the sum of all integers met so far, and after finishing each level add running to the answer. An integer first met at depth d is added once for each level d, d + 1, …, maxDepth, which is exactly maxDepth - d + 1 times, so maxDepth never has to be known in advance.
- level = top-level elements, running = 0, total = 0.
- While level is not empty: for each element, add integers to running and collect the elements of sub-lists into the next level.
- After each level, total += running, then move to the next level.
- Return total.
class Solution {
public int depthSumInverse(List<NestedInteger> nestedList) {
List<NestedInteger> level = new ArrayList<>(nestedList);
int running = 0, total = 0;
while (!level.isEmpty()) {
List<NestedInteger> next = new ArrayList<>();
for (NestedInteger ni : level) {
if (ni.isInteger()) running += ni.getInteger();
else next.addAll(ni.getList());
}
total += running;
level = next;
}
return total;
}
}class Solution:
def depthSumInverse(self, nestedList: List["NestedInteger"]) -> int:
level = list(nestedList)
running = 0
total = 0
while level:
nxt = []
for ni in level:
if ni.isInteger():
running += ni.getInteger()
else:
nxt.extend(ni.getList())
total += running
level = nxt
return totalclass Solution {
public:
int depthSumInverse(vector<NestedInteger>& nestedList) {
vector<const NestedInteger*> level;
for (const NestedInteger& ni : nestedList) level.push_back(&ni);
int running = 0, total = 0;
while (!level.empty()) {
vector<const NestedInteger*> next;
for (const NestedInteger* ni : level) {
if (ni->isInteger()) {
running += ni->getInteger();
} else {
for (const NestedInteger& child : ni->getList()) next.push_back(&child);
}
}
total += running;
level = std::move(next);
}
return total;
}
};function depthSumInverse(nestedList) {
let level = [...nestedList];
let running = 0, total = 0;
while (level.length > 0) {
const next = [];
for (const ni of level) {
if (ni.isInteger()) running += ni.getInteger();
else next.push(...ni.getList());
}
total += running;
level = next;
}
return total;
}Edge cases to test
- A flat list: maxDepth is 1, so the answer is the plain sum
- One deeply nested integer next to shallow ones: the shallow ones get the large weights
- Negative integers
- Integers at the deepest level always have weight 1
Hints
Hint 1
The weight of an integer at depth d is maxDepth - d + 1. If you knew maxDepth, this would be the same as the ordinary weighted sum.
Hint 2
Two passes work: one to find maxDepth, one to add value × (maxDepth - depth + 1).
Hint 3
One pass is possible with BFS: keep a running sum of all integers seen so far and add it to the answer once per level. An integer at depth d is then counted once for every level from d down to maxDepth.
FAQ
What is the best time complexity for Nested List Weight Sum II?
Optimal (one-pass BFS with running sum) runs in O(N) time and O(N) extra space. Each integer and list is handled exactly once.
Which pattern does Nested List Weight Sum II 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 II?
Yes. Two-pass DFS takes O(N) time and O(D) space. First walk the structure recursively to find the deepest level that holds an integer.
Which edge cases should I test for Nested List Weight Sum II?
A flat list: maxDepth is 1, so the answer is the plain sum; One deeply nested integer next to shallow ones: the shallow ones get the large weights; Negative integers; Integers at the deepest level always have weight 1.