Nested List Weight Sum II
Problem
Given a nested list, weight integers by depthFromBottom — leaves at the deepest level get weight 1, the root level gets the max depth.
[1,[4,[6]]]17def depth_sum_inverse(nested):
def depth(items):
d = 1
for x in items:
if isinstance(x, list): d = max(d, depth(x) + 1)
return d
D = depth(nested)
def go(items, d):
s = 0
for x in items:
if isinstance(x, int): s += x * (D - d + 1)
else: s += go(x, d + 1)
return s
return go(nested, 1)function depthSumInverse(nested) {
function depth(items) {
let d = 1;
for (const x of items) if (Array.isArray(x)) d = Math.max(d, depth(x) + 1);
return d;
}
const D = depth(nested);
function go(items, d) {
let s = 0;
for (const x of items) {
if (Array.isArray(x)) s += go(x, d + 1);
else s += x * (D - d + 1);
}
return s;
}
return go(nested, 1);
}class Solution {
public int depthSumInverse(List nested) {
int D = depth(nested);
return go(nested, 1, D);
}
int depth(List items) {
int d = 1;
for (NestedInteger x : items) if (!x.isInteger()) d = Math.max(d, depth(x.getList()) + 1);
return d;
}
int go(List items, int d, int D) {
int s = 0;
for (NestedInteger x : items) {
if (x.isInteger()) s += x.getInteger() * (D - d + 1);
else s += go(x.getList(), d + 1, D);
}
return s;
}
} class Solution {
int depth(vector& items) {
int d = 1;
for (auto& x : items) if (!x.isInteger()) d = max(d, depth(x.getList()) + 1);
return d;
}
int go(vector& items, int d, int D) {
int s = 0;
for (auto& x : items) {
if (x.isInteger()) s += x.getInteger() * (D - d + 1);
else s += go(x.getList(), d + 1, D);
}
return s;
}
public:
int depthSumInverse(vector& nested) {
int D = depth(nested);
return go(nested, 1, D);
}
}; Explanation
The twist in this version is that weight is upside down: the deepest integers get weight 1, and integers near the top get the biggest weight. To assign weights, we first need to know how deep the structure goes.
So the solution does two passes. The first, depth(items), recurses through the nested lists to find the maximum depth D. The second, go(items, d), walks again and for each integer adds x * (D - d + 1).
That weight formula is the heart of it: an integer at depth d sits (D - d + 1) levels above the bottom, so a top-level number gets the largest multiplier and a deepest number gets 1.
Example: [1,[4,[6]]] has max depth D = 3. The 1 at depth 1 weighs 3, the 4 at depth 2 weighs 2, and the 6 at depth 3 weighs 1. Total = 1·3 + 4·2 + 6·1 = 17.
Both passes visit every element once, and the recursion only stacks as deep as the nesting, so it stays simple and linear.