Multi dimensional array cumulative sum in Javascript

Question

Given a multi-dimensional array:

var a = [[3,2,5], [4,1,7], [1,6,8]];

I would like to do a cumulative sum of each array to return the following result:

[[3,2,5], [7,3,12], [8,9,20]];

cum sum on 1st elements of each sub-array: 3 4 1
cum sum on 2nd elements of each sub-array: 2 1 6
cum sum on 3rd elements of each sub-array: 5 7 8

I've tried using reduce(), but can't quite get the expected result.

Any suggestions, much appreciated.

S

UPDATE - Taking it to the next level:

var a = [
    [new Date(), 3,2,5], 
    [new Date(), null,1,7], 
    [new Date(), null,6,8], 
    [new Date(), 1,2,3]
];

Should result in:

[[new Date(), 3,2,5], 
 [new Date(), null,3,12],
 [new Date(), null,9,20],
 [new Date(), 4,11,23]]

My approach was to create a multi-dimensional offsetIndex array:

var offsetIdx = [];
        for (var i=1; i<a.length; i++) {

            for (var z=0; z<a[i].length; z++) {
                var zValue = a[i][z];

                oIdx = offsetIdx[z] || 0;

                a[i][z] = zValue && z!==0 ? a[i-1-oIdx][z] + zValue : zValue;

                if(!zValue){
                    offsetIdx[z] = oIdx + 1;
                } else {
                    offsetIdx[z] = 0; 
                }
            }
        }

Happy to see other approaches and ways of making it ultra light-weight.

How is it that your output array can have the same number of elements, given that a sum will be applied to the input? — New Alexandria
– New Alexandria, Commented Mar 24, 2016 at 2:47
@NewAlexandria: He's accumulating the result as he goes along into each array, so the first array doesn't change, the second is the sum of the first plus itself (for each member respectively), the third is the sum of the result of the second, again plus its own respective members, and so on. — user1106925
– user1106925, Commented Mar 24, 2016 at 2:50
Correct. I leaned towards the reduce() function as it passes a reference to the previous element. I've seen examples with flat 1 dim arrays, but can't quite adapt it to accommodate a multi-dim array. — Seb
– Seb, Commented Mar 24, 2016 at 2:54
It would help if you post your reduce() code. It should work and I'd like to see what you're doing wrong (or I'm doing wrong) if it's not. — djechlin
– djechlin, Commented Mar 24, 2016 at 3:10

char · Accepted Answer · 2016-03-24 02:52:01Z

3

for (var i=1; i<a.length; i++) {
  for (var z=0; z<a[i].length; z++) {
   a[i][z] = a[i-1]][z] + a[i][z]
  }
}

The array should be updated dynamically as the loop runs on. This is destructive so it will modify the original array.

answered Mar 24, 2016 at 2:52

char

915 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Seb Over a year ago

Thanks guys, all viable solutions. I like @char approach as it's light-weight, uses vanilla JS and ultra-fast. Nice one.

char Over a year ago

Thanks for the comment Seb. I got told off by my employer when I opted to use libraries or non loop methods as they make things slower.

djechlin Over a year ago

@char educate your employer on how more maintainable code and fewer bugs is more important than unmeasured speed gains :)

afuous · Accepted Answer · 2016-10-02 01:25:28Z

3

  function cumulativeSum(arr) {
    var result = [arr[0]];
    for(var i = 1; i < arr.length; i++) {
        result.push([]);
        for(var j = 0; j < arr[0].length; j++) {
          result[i].push(result[i - 1][j] + arr[i][j]);
        }
    }
    return result;
}
    
document.body.innerHTML = JSON.stringify(cumulativeSum(
  [[3,2,5], [4,1,7], [1,6,8]]
))

Unlike the other answer, this one is not destructive, preserving the original array and returning the result.

edited Oct 2, 2016 at 1:25

answered Mar 24, 2016 at 2:56

afuous

1,49810 silver badges12 bronze badges

4 Comments

char Over a year ago

This one won't work as the previous result will not be updated. For example when you reach the 3rd array, the 2nd array has not been updated yet to include the first arrays sum, so you will only be getting 2nd array + 3rd array values instead of 1st + 2nd + 3rd array values.

user1106925 Over a year ago

@char: It does work because he's taking the previous values from the result, not the original.

afuous Over a year ago

@char jsfiddle.net/hojwxane It does work. The reason is that the result array does store the original the cumulative sum and the next element is set to be the sum of the previous element of the result array and the next element of the original array.

char Over a year ago

Woops my bad didn't see he was using the results value.

adeneo · Accepted Answer · 2016-03-24 04:30:34Z

Using Array.reduce, it would look like this

var arr  = [[3,2,5], [4,1,7], [1,6,8]];

var arr2 = arr.reduce(function(a,b) {
    var nested = Array.isArray(a[0]);
    b = b.map(function(x,i) {
    	return x + (nested ? a[a.length-1] : a)[i];
    });
    if ( nested ) a.push(b);
    return nested ? a : [a,b];
});

document.body.innerHTML = '<pre>' + JSON.stringify(arr2, 0, 4) + '</pre>';

Here's a sligthly "optimized" (golfed) version, passing in a starting point for the reduction and slicing the array

var arr  = [[3,2,5], [4,1,7], [1,6,8]];

var arr2 = arr.slice(1).reduce(function(a,b) {
	return [a.push(b.map(function(x,i) {return x+a[a.length-1][i]})), a].pop();
},[arr[0]]);

document.body.innerHTML = '<pre>' + JSON.stringify(arr2, 0, 4) + '</pre>';

Making it a one-liner by using ES2015

var arr  = [[3,2,5], [4,1,7], [1,6,8]];
var a2 = arr.slice(1).reduce((a,b)=>[a,a.push(b.map((x,i)=>x+a[a.length-1][i]))][0],[arr[0]]);

document.body.innerHTML = '<pre>' + JSON.stringify(a2, 0, 4) + '</pre>';

djechlin · Accepted Answer · 2016-03-24 02:55:53Z

0

This will give you the sum across all elements. Not quite what you ask, but I will leave this answer here for future visitors who catch the question title.

Flatten first using your favorite library (underscore and lodash both have it)

Then reduce + sum .

_.flatten([1, [2, [3, [4]], 5]]);
// → [1, 2, [3, [4]], 5]

answered Mar 24, 2016 at 2:55

djechlin

61.1k40 gold badges173 silver badges300 bronze badges

Comments

Community · Accepted Answer · 2017-05-23 12:00:53Z

0

What a mathy question.

Why not transpose the array first? An answer on this question - Transposing a 2D-array in JavaScript - suggests the underscore.js solution:

_.zip.apply(_, [[1,2,3], [1,2,3], [1,2,3]])

to do this. There are many ways.

Then the sum should be much easier - just .map(f) where f is your sum on one array function.

IMO this is a good and readable solution, because "transpose+sum" is very true to the column-sum nature of the question, and I would avoid an imperative or loop-heavy solution that obscures this.

edited May 23, 2017 at 12:00

CommunityBot

11 silver badge

answered Mar 24, 2016 at 2:59

djechlin

61.1k40 gold badges173 silver badges300 bronze badges

Collectives™ on Stack Overflow

Multi dimensional array cumulative sum in Javascript

5 Answers 5

3 Comments

4 Comments

Comments

Comments

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

3 Comments

4 Comments

Comments

Comments

Comments

Linked

Related