# Maxcounters in JavaScript

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) {
counters[A[K] - 1] = counters[A[K] - 1] + 1;
// update maximum
if (counters[A[K] - 1] > max) {
max = counters[A[K] - 1];
}
}
}

return counters;
}

• Welcome to Code Review. If you include the description of the task and examples of input and output expected, you have a greater possibility to obtain more detailed answers. May 24, 2020 at 14:58
• Your title is too generic. Please read the appropriate pages in the Help center. May 24, 2020 at 15:19

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.

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