Problem

I have a function that calculates the biggest number in an array after doing the following:

```
arrayManipulation(4, [[2, 3, 603], [1, 1, 286], [4, 4, 882]])
```

The array initially consists of only zeroes. The first parameter tells what the length of the array of 0s should be.

Here it’s 4, so `[0,0,0,0]`

The second parameter is an array of arrays. Each nested array has 3 values. The start index, last index and the value to add to the `zeroArray`

between the two indices. The `zeroArray`

index starts from 1.

For example, in the beginning the zero array is [0,0,0,0]. Then from the nested array `[2, 3, 603]`

, add 603 at indices from 2 to 3. So the zero array becomes `[0,603,603,0]`

. Then the second nested array is used. This is done till all the nested arrays are used.

After that’s done, I need to find the biggest number in the zeroArray(its value now is `[ 286, 603, 603, 882]`

) which here is 882.

I am trying this here, but it timed out.

```
function arrayManipulation(n, operations) {
let zeroArray = Array(n);
zeroArray.fill(0, 0, zeroArray.length);
let biggest = 0;
for (let j = 0; j < operations.length; j++) {
let startIndex = operations[j][0];
let endIndex = operations[j][1];
let number = operations[j][2];
for (let k = startIndex; k <= endIndex; k++) {
zeroArray[k - 1] += number;
if (biggest < zeroArray[k - 1]) {
biggest = zeroArray[k - 1];
}
if (k == endIndex)
console.log(startIndex, endIndex, number, JSON.parse(JSON.stringify(zeroArray)));
}
}
console.log(biggest);
return biggest;
}
```

Solution

The challenge only asks for the biggest number after all operations.

Printing the complete array after each operation might cause it to fail –

either by the unexpected output or by the time spent for the log operation.

Also, determining the maximum after each operation is inefficient, this is

better done after all operations.

But what you actually need to pass the challenge is a better algorithm.

The inner loop

```
for (let k = startIndex; k <= endIndex; k++)
```

takes too much time because it is executed up to 107

${10}^{7}$ times, according

to the given limits.

The crucial idea is not to execute the operations “verbatim,” but to

store and update at each array index the “cumulative increment/decrement” with respect

to the preceding element after all operations encountered so far.

This requires only 2 updates for each operation, plus a final run over

all array elements to find the maximum value.

I don’t want to deprive you from the joy to figure out the concrete code

yourself, but you’ll find more information at Maximum value in an array after m range increment operations, if necessary.