Nested List Weight Sum
Problem
Given a nested list of integers, return the sum of each integer multiplied by its depth.
[[1,1],2,[1,1]]10def depth_sum(nested):
def go(items, depth):
s = 0
for x in items:
if isinstance(x, int): s += x * depth
else: s += go(x, depth + 1)
return s
return go(nested, 1)function depthSum(nested) {
function go(items, depth) {
let s = 0;
for (const x of items) {
if (Array.isArray(x)) s += go(x, depth + 1);
else s += x * depth;
}
return s;
}
return go(nested, 1);
}class Solution {
public int depthSum(List nested) { return go(nested, 1); }
int go(List items, int depth) {
int s = 0;
for (NestedInteger x : items) {
if (x.isInteger()) s += x.getInteger() * depth;
else s += go(x.getList(), depth + 1);
}
return s;
}
} class Solution {
int go(vector& items, int depth) {
int s = 0;
for (auto& x : items) {
if (x.isInteger()) s += x.getInteger() * depth;
else s += go(x.getList(), depth + 1);
}
return s;
}
public:
int depthSum(vector& nested) { return go(nested, 1); }
}; Explanation
Think of the nested list as a tree: the outer list is depth 1, anything one level of brackets deeper is depth 2, and so on. We just need to add up each integer multiplied by its depth, and a simple DFS with a depth counter does exactly that.
The helper go(items, depth) loops through the list. When it meets a plain integer it adds x * depth to the running sum. When it meets a sub-list it recurses with depth + 1.
Passing depth + 1 into each nested call is the whole trick — it keeps track of how deeply buried the current numbers are without any extra bookkeeping.
Example: [[1,1],2,[1,1]]. The four 1s sit at depth 2 and the 2 sits at depth 1, so the sum is 1·2 + 1·2 + 2·1 + 1·2 + 1·2 = 10.
Every element is visited once and the recursion only goes as deep as the nesting, so it is a clean linear pass.