Nested List weight sum javascript

nested list weight sum ii
nested list weight sum youtube
nested list weight sum @ python

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/)

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]));

Nested List Weight Sum algorithm issue, You could use Array#reduce and omit the sum for every level by returning a sum for each level. function depthSum(nestedList, level = 1)  Search less. Build more. Use Stack Overflow for Teams at work to share knowledge with your colleagues. Free 30 day trial. Start your trial.

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.

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:

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

JavaScript LeetCode 339: Nested List Weight Sum (Cat Racket , var depthSum = function(nestedList) { let sum = 0; return helper(nestedList,1); function helper(list,level){ let sum = 0; //reset sum for each depth  LeetCode – Nested List Weight Sum (Java) Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list -- whose elements may also be integers or other lists.

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]],[]]));

339. Nested List Weight Sum · Issue #91 · jzhangnu/Leetcode-JS , listWeightSum.js. /*. * Given a nested list of integers, return the sum of all integers in the list weighted by their depth. *. * Each element is either an integer, or a list  LeetCode – Nested List Weight Sum II (Java) Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list -- whose elements may also be integers or other lists.

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]]));

leetcode: 339. Nested List Weight Sum · GitHub, Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list  The above algorithm to compute the nested weight list sum runs at O(N) time where N is the number of integers in the list including the sub-list as each integer is visited exactly once. In the worst case for inputs like [1, [1, [1, [1, ..] ..

How to Compute Nested List Weight Sum of Any Arrays , class NestedList(): def __init__(self, vals): self.content = vals def weightSum(self): return self.weightSumHelper(1) def weightSumHelper(self, depth): result = 0  Fenwick Tree and Leetcode 307 | Range Sum Query - Mutable | Company Tag: Google Facebook - Duration: 29:33. Nideesh Terapalli 1,000 views

Nested list of int array, Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list  Given a nested list (where sublists are of equal length), write a Python program to find the column-wise sum of the given list and return it in a new list. We can find sum of each column of the given nested list using zip function of python enclosing it within list comprehension. Another apporach is to use map ().

/** * Given a nested list o, Given a nested list of integers, returns the sum of all integers in the list weighted by their depth * For example, given Returns the nested list that this NestedInteger holds, if it holds a nested list // Returns null if this Using javascript: var total  339 Nested List Weight Sum.js; 34 Search for a Range.js; 340 Longest Substring With At Most K Distinct Characters.js; 341 Flatten Nested List Iterator.js; Design Tic-Tac-Toe.java; 349 Intersection of Two Arrays.js; 35 Search Insert Position.js; 350 Intersection of Two Arrays II.js; 353 Design Snake Game.js; 36 Valid Sudoku.js; 364 Nested List

Comments
  • I'd traverse to find the max depth and then apply your previous algorithm in a second traversal. The link is for premium members only.
  • Thanks for the input ggorlen, can you enlighten me on how it works? Should i do like a DFS on array and find max depth first?
  • It's not really a DFS or BFS because you'd have to search the entire structure, so any full traversal will do. I'll post some code, but I can't validate it on your link.
  • ggorlen is right. It needs two traversals - one to find max depth and then one to calculate the result. A queue based BFS would do for both.
  • You don't need two traversals if you keep a list of the totals per level, and then multiply them by their depth after the traversal.
  • Thanks for sharing this awesome piece. Thank you!
  • What an amazing solution. Thank you so much. Will go through it in depth!
  • I think this solves the basic version, not the reverse weight version.
  • @m69 Yes right.. Thanks for the heads up.. I have added a proper approach. Your solution though, is also traversing around the same number of times is what i think.
  • Well, the input array is always longer and/or higher-dimensional than the sums array, so I assume it'll be faster in practice, even if the theoretical time complexity for all approaches is O(N).