Ok the Max Counters problem is the first algo challenge marked as medium in the codility lessons.<\/p>\n\n\n\n
I devised a O(m+n) solution.<\/p>\n\n\n\n
We first check if there’s no element N+1 in the array we just run the through the array and increment the counters at the end. <\/p>\n\n\n\n
For the case when N+1 is present in the array, we run through the array increasing the counters while A[K] = X < N+1. We keep in the variable max the maximum available counter for the moment when we will have to update all.<\/p>\n\n\n\n
When N+1 is met we update all counters to the max value. If the next element is again N+1 we just continue the iteration, as we don’t have a new counter to update since there was no incrementation since the last update.<\/p>\n\n\n\n
function solution(N, A) {\n let counters = Array (N).fill(0)\n \/\/take care of the case when there is no element === N+1\n \/\/simply run through the array and return the counters at the end\n if (A.indexOf(N+1) === -1){\n for (let j = 0; j < A.length; j++){\n counters[A[j]-1]++ \n }\n return counters\n }\n\n let max = min = maxSum = 0\n let nextSkip = 0\n \n for (let i = 0; i < A.length; i ++){\n if (A[i] < N + 1){\n nextSkip = 0\n counters[A[i]-1]++\n \/\/we check and keep a record of the max counter\n if (counters[A[i]-1] > max) {\n max = counters[A[i]-1]\n }\n } else if (A[i] === N + 1 && nextSkip === 0){\n nextSkip = 1\n for (let j =0; j < counters.length; j++){\n counters[j] = max\n }\n }\n }\n return counters\n \n}<\/code><\/pre>\n\n\n\n