Nested List weight sum javascript

I'm trying to work on this problem where we compute Nested weight sum for a given array of numbers.

Given a nested list of integers, return the sum of all integers in the
list weighted by their depth.

For example for:

[[1,1],2,[1,1]] ====> solution is 10.

Four 1's at depth 2, one 2 at depth 1.

Here's the code i wrote:

var depthSum = function (nestedList, sum=0, depth=1)
for(let i=0; i<nestedList.length; i++)
let val = nestedList[i];
if (Array.isArray(val))
return depthSum(val, sum, depth+1);
else
sum += val * depth;

;
return sum;
;


I'm trying to work on the converse problem. i.e

Given a nested list of integers, return the sum of all integers in the
list weighted by their depth. Where weight is increasing from root to
leaf, now the weight is defined from bottom up. i.e., the leaf level
integers have weight 1, and the root level integers have the largest
weight.

Example:
[[1,1],2,[1,1]] ===> Solution is 8.

How can I use the same approach and solve this problem?

(https://leetcode.com/problems/nested-list-weight-sum-ii/description/)

4 Answers
4

This should do the job, but I wish I had a premium leetcode account to verify that. The idea is to do a search to find the maximum depth in the structure, then use your previous algorithm but with the depth calculation inverted. Also, doing it without recursion means less chance of timing out and no chance of blowing the stack. I added a few basic test cases, but again, no guarantees.

const search = a =>
let sum = 0;
let depth = 0;
const stack = [[a, 0]];

while (stack.length)
const curr = stack.pop();

if (curr[1] > depth)
depth = curr[1];


for (const e of curr[0])
if (Array.isArray(e))
stack.push([e, curr[1] + 1]);




stack.push([a, ++depth]);

while (stack.length)
const curr = stack.pop();

for (const e of curr[0])
if (Array.isArray(e))
stack.push([e, curr[1] - 1]);

else
sum += e * curr[1];




return sum;
;

console.log(search([[1,1],2,[1,1]]));
console.log(search());
console.log(search([6]));
console.log(search([[[[3]]]]));
console.log(search([[2],1]));

A basic recursive solution alone like your original depthSum probably won't work for the second requirement, because you need to figure out the total depth before you know the multiplier for the items on the top level of the array. One option is to figure out the depth of the deepest array first, and then use something similar to your original depthSum.

depthSum

depthSum

You can use reduce (which is the appropriate method to use to convert an object into a single value) and the conditional (ternary) operator to make your code concise and less repetitive:

reduce

const depthCheck = (item) => (
Array.isArray(item)
? 1 + Math.max(...item.map(depthCheck))
: 0
);

// verification:
console.log(depthCheck([[1,1],2,[1,1]])); // total depth 2
console.log(depthCheck([[1,1],2,[1,1,[2,2]]])) // total depth 3
console.log(depthCheck([[1,1,[2,[3,3]]],2,[1,1,[2,2]]])) // total depth 4
console.log('-----')

const depthSum = (nestedList, weight=depthCheck(nestedList)) => (
nestedList.reduce((a, val) => a + (
Array.isArray(val)
? depthSum(val, weight - 1)
: val * weight
), 0)
);

console.log(depthSum([[1,1],2,[1,1]])) // (2)*2 + (1+1+1+1)*1
console.log(depthSum([[1,1],2,[1,1,[2,2]]])) // (2)*3 + (1+1+1+1)*2 + (2+2)*1
console.log(depthSum([[1,1,[2,[3,3]]],2,[1,1,[2,2]]])) // (2)*4 + (1+1+1+1)*3 + (2)*2 + (3+3)*1

You can do this without needing two traversals of the nested array, if you store the sums of the elements per depth in an array during the traversal. Afterwards, you know that the length of this array is the maximum depth, and you can multiply the sums by their correct weight.

The traversal can be done using recursion or a stack, as explained in the other answers. Here's an example using recursion:

function weightedSum(array)
var sums = , total = 0;
traverse(array, 0);
for (var i in sums)
total += sums[i] * (sums.length - i);
return total;

function traverse(array, depth)
if (sums[depth] === undefined)
sums[depth] = 0;
for (var i in array)
if (typeof array[i] === "number")
sums[depth] += array[i];
else traverse(array[i], depth + 1);




console.log(weightedSum([,]));
console.log(weightedSum([[1,1],2,[1,1]]));
console.log(weightedSum([1,[,2,2],1,[[3,3,[[5]]],[3]],]));

May be you can do as follows with a simple recursive reducer.

var weightOfNested = (a,d=1) => a.reduce((w,e) => Array.isArray(e) ? w + weightOfNested(e,d+1)
: w + d*e, 0);
console.log(weightOfNested([[1,1,[3]],2,[1,1]]));

So OK as mentioned in the comment the above code is weighing the deeper elements more. In order to weigh the shallow ones more we need to know the depth of the array in advance. I believe this way or that way you end up traversing the array twice... once for the depth and once for calculating the weighted sum.

var weightOfNested = (a, d = getDepth(a)) => a.reduce((w,e) => Array.isArray(e) ? w + weightOfNested(e,d-1)
: w + d*e, 0),
getDepth = (a, d = 1, t = 1) => a.reduce((r,e) => Array.isArray(e) ? r === t ? getDepth(e,++r,t+1)
: getDepth(e,r,t+1)
: r, d);
console.log(weightOfNested([[1,1,[3]],2,[1,1]])); // depth is 3

Thanks for contributing an answer to Stack Overflow!

But avoid …

To learn more, see our tips on writing great answers.

Some of your past answers have not been well-received, and you're in danger of being blocked from answering.

Please pay close attention to the following guidance:

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.