Sum multiple items in 2D array based on condition (javascript)

TopMarx
March 26, 2024
159 views
3 votes
3 Answers

I have a 2D array:

[ [ 1, 2, 43, 5 ],
  [ 1, 5, 12, 1 ],
  [ 2, 3, 6, 77 ],
  [ 2, 1, 48, 94 ],
  [ 3, 3, 15, 85 ],
  [ 3, 7, 97, 86 ],
  [ 4, 0, 9, 54 ],
  [ 4, 1, 83, 16 ]]

This is the result I’m after:

[ [ 1, 7, 55, 6 ],
  [ 2, 4, 54, 171 ],
  [ 3, 10, 112, 171 ],
  [ 4, 1, 92, 70 ]]

Match the first index within each array, and sum the other indexes.

My first thought was to use reduce and findIndex to find the index of the first item, add item to array if not found, otherwise sum the values.

But I really don’t know what I’m doing.

array.reduce((acc,e) => 
      { let index = acc.findIndex(inner => inner[0] === e[0]);
      (index === -1) ? [...acc,e] : (acc[index][1] += e[1]) && (acc[index][2] += e[2]) && (acc[index][3] += e[3]);
      return acc},[]);

Help please!

EDIT: I’m learning! A simple change to my attempt and it worked, thanks for pointing out my error @mykaf and @trincot.

Change made to update accumulator [...acc,e] to acc.push(e)

  const input = [ [ 1, 2, 43, 5 ],
              [ 1, 5, 12, 1 ],
              [ 2, 3, 6, 77 ],
              [ 2, 1, 48, 94 ],
              [ 3, 3, 15, 85 ],
              [ 3, 7, 97, 86 ],
              [ 4, 0, 9, 54 ],
              [ 4, 1, 83, 16 ]];

  const result = input.reduce((acc,e) => 
      { let index = acc.findIndex(inner => inner[0] === e[0]);
      (index === -1) ? acc.push(e) : (acc[index][1] += e[1]) && (acc[index][2] += e[2]) && (acc[index][3] += e[3]);
      return acc;
      },[]);

  console.log(result);

Read on for some excellent/better answers to the problem.

Answers

Using reduce is a good way to do it, but in your attempt you never update the accumulator acc: the callback always returns the same, unmutated acc array.

I would however suggest using a Map or a plain object as your accumulator, so that you don’t need to scan an array with findIndex, but can immediately look up by key. Then when the reducing is complete, you can extract the values from the result.

Here is how that would work:

const arr = [ [ 1, 2, 43, 5 ],
              [ 1, 5, 12, 1 ],
              [ 2, 3, 6, 77 ],
              [ 2, 1, 48, 94 ],
              [ 3, 3, 15, 85 ],
              [ 3, 7, 97, 86 ],
              [ 4, 0, 9, 54 ],
              [ 4, 1, 83, 16 ]];

const result = Object.values(
    arr.reduce((acc, [key, ...rest]) => {
        if (!acc[key]) acc[key] = [key, ...rest];
        else rest.forEach((val, i) => acc[key][i+1] += val);
        return acc;
    }, {})
);
console.log(result);

If you want to optimize for speed, then you’re better off with plain old for loops, and to support any data type for the key column, you would use a Map:

const arr = [ [ 1, 2, 43, 5 ],
              [ 1, 5, 12, 1 ],
              [ 2, 3, 6, 77 ],
              [ 2, 1, 48, 94 ],
              [ 3, 3, 15, 85 ],
              [ 3, 7, 97, 86 ],
              [ 4, 0, 9, 54 ],
              [ 4, 1, 83, 16 ]];

const acc = new Map;
for (let i = 0; i < arr.length; i++) {
    const key = arr[i][0];
    let sub = acc.get(key);
    if (!sub) acc.set(key, arr[i]);
    else {
        const add = arr[i];
        for (let j = 1; j < sub.length; j++) {
            sub[j] += add[j];
        }
    }
}
    
const result = [...acc.values()];
console.log(result);

This faster version mutates the input array. If you don’t want that, you’ll need to spend some processing time to create a new sub array by doing a spread like acc.set(key, [...arr[i]]);

You can use vanilla reverse for-loop along with the function Array.prototype.splice to remove on-the-fly already processed array:

The following approach it’s really fast and creates a copy of the original array to avoid mutation:

const source = [ [ 1, 2, 43, 5 ],
  [ 2, 3, 6, 77 ],
  [ 4, 1, 83, 16 ],
  [ 2, 1, 48, 94 ],
  [ 3, 3, 15, 85 ],
  [ 1, 5, 12, 1 ],
  [ 3, 7, 97, 86 ],
  [ 4, 0, 9, 54 ]];
  
const copyArr = source.slice(0);
  
for (let i = copyArr.length - 1; i >= 0; i--) {
  const array = copyArr[i],
        index = array[0];
  for (let k = copyArr.length - 1; k !== i && k >= 0; k--) {
    if (copyArr[k][0] == index) {
      for (let s = 1; s < copyArr[k].length; s++) {
        array[s] = array[s] + copyArr[k][s];
      }
      copyArr.splice(k, 1);
    }
  }
}
  
console.log(copyArr);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Since your data is sorted by the first index, you can just reduce and if a new index is encountered create new sum arrays otherwise add to the last array. If the input isn’t sorted, just sort:

const input = [ [ 1, 2, 43, 5 ],
              [ 1, 5, 12, 1 ],
              [ 2, 3, 6, 77 ],
              [ 2, 1, 48, 94 ],
              [ 3, 3, 15, 85 ],
              [ 3, 7, 97, 86 ],
              [ 4, 0, 9, 54 ],
              [ 4, 1, 83, 16 ]];

const result = input.sort((a,b) => a[0]-b[0]).reduce((r, arr) => {
  const prev = r.at(-1);
  prev?.[0] === arr[0] ? prev.forEach((n, i) => i && (prev[i] += arr[i])) : r.push(arr.slice());
  return r;
}, []);

console.log(result);

` Chrome/123
-------------------------------------------------------------------------------
>                n=8       |      n=80       |      n=800      |     n=8000    
trincot     1.00x x10m 920 | 1.00x   x1m 858 | 1.00x x100k 845 | 1.00x x10k 852
Alexander   2.36x  x1m 217 | 1.66x x100k 142 | 1.54x  x10k 130 | 1.77x  x1k 151
Ele         1.27x  x1m 117 | 2.37x x100k 203 | 2.47x  x10k 209 | 2.51x  x1k 214
-------------------------------------------------------------------------------
https://github.com/silentmantra/benchmark `

const $chunk = [ [ 1, 2, 43, 5 ],
              [ 1, 5, 12, 1 ],
              [ 2, 3, 6, 77 ],
              [ 2, 1, 48, 94 ],
              [ 3, 3, 15, 85 ],
              [ 3, 7, 97, 86 ],
              [ 4, 0, 9, 54 ],
              [ 4, 1, 83, 16 ]];
const $input = [];
const input = $input;
  
// @benchmark trincot
const acc = new Map;
for (let i = 0; i < input.length; i++) {
  const key = input[i][0];
  let sub = acc.get(key);
  if (!sub) acc.set(key, input[i]);
  else {
      const add = input[i];
      for (let j = 1; j < sub.length; j++) {
          sub[j] += add[j];
      }
  }
}

[...acc.values()];

// @benchmark Ele
const copyArr = input.slice(0);
  
for (let i = copyArr.length - 1; i >= 0; i--) {
  const array = copyArr[i],
        index = array[0];
  for (let k = copyArr.length - 1; k !== i && k >= 0; k--) {
    if (copyArr[k][0] == index) {
      for (let s = 1; s < copyArr[k].length; s++) {
        array[s] = array[s] + copyArr[k][s];
      }
      copyArr.splice(k, 1);
    }
  }
}
copyArr;

// @benchmark Alexander
input.sort((a,b) => a[0]-b[0]).reduce((r, arr) => {
  const prev = r.at(-1);
  prev?.[0] === arr[0] ? prev.forEach((n, i) => i && (prev[i] += arr[i])) : r.push(arr.slice());
  return r;
}, []);

/*@skip*/ fetch('https://cdn.jsdelivr.net/gh/silentmantra/benchmark/loader.js').then(r => r.text().then(eval));

Please signup or login to give your own answer.

Click here to cancel reply.