# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation.
class NestedInteger:
def isInteger(self) -> bool:
pass
def getInteger(self) -> int:
pass
def getList(self) -> ['NestedInteger']:
pass
class Solution:
def depthSumInverse(self, nestedList: [NestedInteger]) -> int:
from collections import deque
level_sums = []
queue = deque(nestedList)
while queue:
level_sum = 0
size = len(queue)
for _ in range(size):
ni = queue.popleft()
if ni.isInteger():
level_sum += ni.getInteger()
else:
queue.extend(ni.getList())
level_sums.append(level_sum)
total = 0
depth = len(level_sums)
for i, s in enumerate(level_sums):
total += s * (depth - i)
return total
// This is the interface for NestedInteger.
// You should not implement it, or speculate about its implementation.
class NestedInteger {
public:
bool isInteger() const;
int getInteger() const;
const vector<NestedInteger> &getList() const;
};
class Solution {
public:
int depthSumInverse(vector<NestedInteger>& nestedList) {
vector<int> levelSums;
queue<NestedInteger> q;
for (auto &ni : nestedList) q.push(ni);
while (!q.empty()) {
int levelSum = 0, size = q.size();
for (int i = 0; i < size; ++i) {
NestedInteger ni = q.front(); q.pop();
if (ni.isInteger()) {
levelSum += ni.getInteger();
} else {
for (auto &child : ni.getList()) q.push(child);
}
}
levelSums.push_back(levelSum);
}
int total = 0, depth = levelSums.size();
for (int i = 0; i < depth; ++i) {
total += levelSums[i] * (depth - i);
}
return total;
}
};
// This is the interface for NestedInteger.
// You should not implement it, or speculate about its implementation.
public interface NestedInteger {
public boolean isInteger();
public Integer getInteger();
public List<NestedInteger> getList();
}
class Solution {
public int depthSumInverse(List<NestedInteger> nestedList) {
List<Integer> levelSums = new ArrayList<>();
Queue<NestedInteger> queue = new LinkedList<>(nestedList);
while (!queue.isEmpty()) {
int levelSum = 0, size = queue.size();
for (int i = 0; i < size; ++i) {
NestedInteger ni = queue.poll();
if (ni.isInteger()) {
levelSum += ni.getInteger();
} else {
queue.addAll(ni.getList());
}
}
levelSums.add(levelSum);
}
int total = 0, depth = levelSums.size();
for (int i = 0; i < depth; ++i) {
total += levelSums.get(i) * (depth - i);
}
return total;
}
}
/**
* // This is the interface for NestedInteger.
* // You should not implement it, or speculate about its implementation.
* function NestedInteger() {
* @return {boolean}
* this.isInteger = function() { ... };
* @return {integer}
* this.getInteger = function() { ... };
* @return {NestedInteger[]}
* this.getList = function() { ... };
* };
*/
/**
* @param {NestedInteger[]} nestedList
* @return {number}
*/
var depthSumInverse = function(nestedList) {
let levelSums = [];
let queue = nestedList.slice();
while (queue.length) {
let levelSum = 0;
let size = queue.length;
for (let i = 0; i < size; ++i) {
let ni = queue.shift();
if (ni.isInteger()) {
levelSum += ni.getInteger();
} else {
queue.push(...ni.getList());
}
}
levelSums.push(levelSum);
}
let total = 0, depth = levelSums.length;
for (let i = 0; i < depth; ++i) {
total += levelSums[i] * (depth - i);
}
return total;
};
You are given a nested list of integers nestedList. Each element is either a single integer or a list of integers (which may itself be nested arbitrarily deep). Your task is to compute the sum of all integers in the list weighted by their inverse depth:
maxDepth - currentDepth + 1, where maxDepth is the maximum depth of any integer in the structure, and currentDepth is the depth of the current integer (root level is depth 1).Constraints: The solution must work for arbitrarily nested lists. There is only one valid answer for each input, and you must not reuse or skip any elements.
At first glance, this problem looks similar to the classic "Nested List Weight Sum" problem, where you multiply each integer by its depth. However, here the twist is that the weight is inversely proportional to its depth: the deeper an integer is, the lower its weight.
The brute-force approach would be to first compute the maximum depth of the structure, and then, in a second pass, sum up all the integers multiplied by their inverse depth. But this requires two traversals.
To optimize, we can think about traversing the structure level by level (breadth-first), recording the sum of all integers at each depth. Since the shallowest levels get the highest weight, we can store the sum at each level in a list, and at the end, multiply each level's sum by the appropriate weight.
This approach helps us avoid recursion stack overflows for very deep structures and makes the computation of weights straightforward.
The solution uses a breadth-first search (BFS) to traverse the nested list level by level. Here is the step-by-step algorithm:
nestedList as the first level in the queue.
level_sums).
maxDepth - currentLevel + 1. Multiply each level's sum by its weight and add to the total.
This approach ensures that each integer is visited exactly once, and the weights are applied correctly according to their inverse depth.
Let's walk through an example with input:
[[1,1],2,[1,1]]
[1,1], 2, [1,1].
2 is an integer, so level 1 sum = 2.[1,1] lists are added to the queue for the next level.[1,1] and [1,1].
This matches the expected output.
The key insight is to process the nested list in a breadth-first manner, collecting the sum at each depth, and then applying the correct inverse weights in a single pass. This avoids recursion and makes the weight calculation straightforward. The algorithm is both time and space efficient, visiting each element only once and using simple data structures to track the computation.