2
\$\begingroup\$

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;

}
\$\endgroup\$
2

1 Answer 1

2
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.