Summing same index values in 2D arrays in javascript

Question

After solving a problem, I came to this conclusion.

let n = 10;
let array = [
  [1, 5, 3],
  [4, 8, 7],
  [6, 9, 1]
];
let answer = array.map((val) => new Float32Array(n).fill(val[2], val[0] - 1, val[1]));
console.log(Math.max(...answer.reduce((r, a) => a.map((b, i) => (r[i] || 0) + b), [])))

Okay, so what this does is it creates an array of n elements with the value of the third element from the index from the range of the first value to the second value.

Indexes start from 1 here.

Like for [1, 5, 3], (n = 10), it creates an array of 10 elements with the value 3 from the index 1 to the index 5 and else everything is just blank or 0.

Then for [4, 8, 7], (n = 10), it creates an array of 10 elements with the value 7 from the index 4 to the index 8 and else, everything is just blank or 0.

Then for [6, 9, 1], (n = 10), it creates an array of 10 elements with the value 1 from the index 6 to the index 9 and else, everything is just blank or 0.

Now we have to sum all the matching columns and return the maximum value, which I do by

Math.max(...answer.reduce((r, a) => a.map((b, i) => (r[i] || 0) + b), []))

Everything works fine and the test cases work but the program is not at all efficent, with refrence to this problem, my code just timeouts.

I think the problem is when I sum the values. That is what is taking the most memory.

What can be an alternate method to sum the same index array values? Being it the most efficient

Answer 1

The problem is, that you create an array of length n for each operation (in the input array), and then sum them by calling reduce on the result and after that you finally find the maximum of that resulting array. But you only need one initial array to sum up in, and you can find the maximum in the same operation - here in a rather verbose form:

function arrayManipulation(n, arr) {
  var res = [];
  var max = 0;

  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < n; j++) {
      if (i === 0) {
        res.push(j >= arr[i][0] - 1 && j <= arr[i][1] - 1 ? arr[i][2] : 0);
      }
      else {
        res[j] += j >= arr[i][0] && j <= arr[i][1] ? arr[i][2] : 0;
      }
      max = Math.max(max, res[j]);
    }
  }
  return max;
}

which can be narrowed down to this more succinct form:

function arrayManipulation(n, arr) {
  var res = [];
  var max = Number.MIN_VALUE;

  for (var i = 0; i < arr.length; i++) {
    for (var j = arr[i][0]; j <= arr[i][1]; j++) {
      res[j] = (res[j] || 0) + arr[i][2];
      max = Math.max(max, res[j]);
    }
  }
  return max;
}

Here is used, that it is only needed to loop through the intervals of the array that is actually manipulated by each operation in the input array. So for instance in the example operations, it is for the first operation only necessary to add 3 to the values in places from 1 to 5 inclusive.

---

Update

Building on the idea from the comment by weegee a modification of my solution above could handle that:

function arrayManipulation(n, arr) {
  arr = arr.sort((a, b) => a[0] < b[0] ? -1 : a[0] === b[0] ? 0 : 1);
  var max = Number.MIN_VALUE;

  for (var i = 0; i < arr.length; i++) {
    var sum = arr[i][2];
    for (var j = i + 1; j < arr.length; j++) {
      if (arr[j][0] <= arr[i][1])
        sum += arr[j][2];
      else
        break;
    }
    max = Math.max(sum, max);
  }

  return max;
}

First the operations are sorted according to their start position (first element in the sub array), and then the operations are iterated and summed up as long as there is an overlap from operation to operation. Finally the current sum is compared to the existing maximum sum in max.