https://leetcode.com/problems/nested-list-weight-sum-ii/
For this problem you are given a list of NestedIntegers, a data structure that is loosely defined as follows, a nested integer is either an integer or a list of integers. The question goes as follows given a list of NestedIntegers find the nested list weight sum which is the sum of the integers in the list weighted by depth such that the integers in a list of integers have 1 less in weight than the ones outside. Complete description in the problem link.
For example in [1, [4, [6]]] 1 has weight 3, 4 has weight 2 and 6 has weight 1. Their sum is 17.Solution
The solution I came up with for this problem requires 2 passes of the list with a runtime complexity of O(2*n) where n is the total number of integers.
On the first pass we find the maximum depth of the list
On the second pass we compute the sum with this maximum depth. for the second we keep track of the depth of the current NestedInteger and to compute the weighted sum we subtract the current depth from the maximum depth plus 1 and add this to the sum. Applying this logic recursively solves the problem.
class Solution {
public:
int helper(vector<NestedInteger>& nestedList, int currMax) {
int maxim = currMax;
for(int i = 0; i < nestedList.size(); i++){
NestedInteger current = nestedList[i];
if(current.isInteger()){
continue;
}else{
maxim = max(helper(current.getList(), 1+currMax), maxim);
}
}
return maxim;
}
int helper2(vector<NestedInteger>& nestedList, int maxAllTime, int depth) {
int sum = 0;
for(int i = 0; i < nestedList.size(); i++){
NestedInteger current = nestedList[i];
if(current.isInteger()){
sum+=current.getInteger()*(maxAllTime-depth+1);
}else{
sum+=helper2(current.getList(), maxAllTime, depth+1);
}
}
return sum;
}
int depthSumInverse(vector<NestedInteger>& nestedList) {
int maxAllTime = helper(nestedList, 1);
int res = helper2(nestedList,maxAllTime, 1 );
return res;
}
};