Maxcounters in JavaScript

Question

I am trying to solve this question: MaxCounters.

Solving it is straightforward, but solving it fast enough is proving very difficult. How can I improve the performance of this code? At the moment it is too slow for the large_random_2 and extreme_large tests.

function solution(N, A) {
    const M = A.length;
    let max = 0;
    let counters = new Array(N);

    if (M <= 0) {
        return -1;
    }

    // set counters to 0
    for (let i = 0; i < N; i++) {
        counters[i] = 0;
    }

    for (let K = 0; K < M; K += 1) {
        if (A[K] === N + 1) {
            // set counters to last maximum
            for (let j = 0; j < N; j++) {
                counters[j] = max;
            }
        } else if (A[K] > 0 && A[K] <= N) {
            // add one to counter
            counters[A[K] - 1] = counters[A[K] - 1] + 1;
            // update maximum
            if (counters[A[K] - 1] > max) {
                max = counters[A[K] - 1];
            }
        }
    }

    return counters;
}

Answer 1

You can save some time by not running through every counter and setting them to the maximum each time max gets called. Since they are all equivalent at the start and after each time the max is called, you can just record the current maximum counter value (in between each call of max) and add it all together at the end, rather than updating every counter element each time max is called.

let currentTally = {};
let currentMax = 0;
let total = 0;
for (let K = 0; K < M; K += 1) {
        if (A[K] <= N) {
             if(currentTally[A[K]]){
                 currentTally[A[K]] += 1;
             }else {
                 currentTally[A[K]] = 1;
             }
             if( currentTally[A[K]] > currentMax) {
                  currentMax = currentTally[A[K]];
             }
        }

        if (A[K] === N + 1) {
            total += currentMax;
            currentTally = {};
            currentMax = 0;
        } 
        }
    }
    for(let i = 0; i < counters.length; i++) {
         if(currentTally[i]){
             counters[i] = total + currentTally[i];
         }else{
             counters[i] = total;
         }
    }

Also, this way, no need to set all counters to zero in the first place.

Answer 2

Algorithm

As the answer by eaeaoo implies, the runtime complexity can be reduced to \$O(N+M)\$ by keeping track of the minimum baseline (max counter to set all to). This aligns with other solutions (e.g. this python comparison).

To minimize the space complexity even more, the data structure for the tallies can remain in an array instead of an object/map, and a second variable for the "last" max -e.g. lastMax can be used to track the most recent maximum value to use in the second loop.

let currentMax = 0;
let lastMax = 0;
const M = A.length;
const counters = Array(N).fill(0);
for (const currentValue of A) {
    if (currentValue > N) {
        lastMax = currentMax             
    } 
    else {
         const position = currentValue - 1;
         if (counters[position] < lastMax) {
             counters[position] = lastMax;
         }
         counters[position]++;
         if (counters[position] > currentMax) {
             currentMax = counters[position];
        }
    }
}
for (let i = 0; i < N; i++) {
    if (counters[i] < lastMax) {
        counters[i] = lastMax;
    }
}
return counters;

Review of current code

One of the first blocks is this:

if (M <= 0) {
    return -1;
}

That is good to do, though the description reads:

A non-empty array A of M integers is given.

It doesn't hurt to check for that condition but know that it shouldn't happen. If you are going to have it then have it return as early as possible so as to minimize memory allocation and processing - e.g. before declaring other variables like max and counters.

This block initializes values to 0:

// set counters to 0
for (let i = 0; i < N; i++) {
    counters[i] = 0;
}

Instead consider using Array.fill(0) like the code in the sample code above uses. This allows counters to be declared with const since the array itself wouldn't need to be re-assigned. This helps avoid accidental re-assignment later when modifying your code.

const counters = Array(N).fill(0);

And the for loop:

for (let K = 0; K < M; K += 1) {

Can be replaced with a for...of loop (as used in the sample code above) since K is only used to dereference indexes in A.