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
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.