In a nutshell:
N is an integer that represents a number of counters and the max counter allowed;A is an array that represents the operation done on a specific counter (for example, if A[0] is 1 and N is 3, we need to add 1 to counter[0]);A is N+1, all elements of the counter should be changed to the largest number in the counter array.I submitted the code I wrote and got only 60% in performance. Why is that? Any way I should approach a problem next time to make it more efficient? How can I improve?
function solution(N,A){
let counters = Array(N).fill(0);
let maxCounter = 0;
for(i=0;i<A.length;i++){
if(A[i]<=N){
counters[A[i]-1]++
if(counters[A[i]-1]>maxCounter){maxCounter = counters[A[i]-1]};
}
else if(A[i]===N+1){
counters = Array(N).fill(maxCounter)
}
}
return counters
}
Edit: I didn't know that this website wasn't meant for questions regarding code improvement, thanks, I will ask somewhere else.
One possible improvement would be, when you need to fill the whole array with the new max counters, don't create an entirely new array to do so - instead, change the existing array.
else if(A[i]===N+1){
counters.fill(maxCounter)
}
This could have a large effect if there are a whole lot of counters.
Here is a solution using object which will generate the actual array only once (after all operations are applied).
The "tracker" object will only ever hold the indices & values of those counters which have an operation. Say, N (ie, "num" number of counters) is 50,000 but only 5,000 counters have an explicit operation in A (ie, "arr" array), only those 5,000 elements will be tracked (using the "tracker" object).
Code Snippet
// alternative solution using object
const counterOps = (num, arr) => {
// the "tracker" object we will use to populate the result array
const tracker = {};
// when "num+1" to reset all elements to "max", then
// the "max" value is stored in "lastMaxSet"
let lastMaxSet = 0;
// helper method to get current max from "tracker"
const getMax = obj => Math.max(...Object.values(obj));
// helper method to "set" "all" values to "max"
const setMax = obj => {
lastMaxSet = getMax(obj);
Object.keys(obj).forEach(k => obj[k] = lastMaxSet);
};
// iterate through "arr" and "apply" each "operation"
arr.forEach(elt => {
if (elt === num + 1) {
// "reset to max" operation is applied
setMax(tracker);
} else {
// a particular counter is incremented
const k = elt - 1;
tracker[k] ??= lastMaxSet;
tracker[k]++;
}
});
// the "tracker" object is used to generate
// the result-array on-the-fly
return [...Array(num).fill(lastMaxSet)].map(
(val, idx) => idx in tracker ? tracker[idx] : val
);
};
console.log(counterOps(5, [3, 4, 4, 6, 1, 4, 4]));.as-console-wrapper { max-height: 100% !important; top: 0 }Please try out and share feedback if it helped at all (with performance).
The 60% score for efficiency is because of the two last test cases where over 10,000 "max counter" operations get performed. https://app.codility.com/demo/results/trainingA86B4F-NDB/
Each of those operations has to iterate through the counter array, which may have as many as 100,000 elements. That works out to a total of 1 billion writes, so the reason for the performance problem comes quickly in sight.
To improve this and bring this number down, we can eliminate the needless consecutive "max counter" operations by, for example, introducing a flag denoting whether the counter array is already maxed and there is no need to iterate through it all over again.
Sample code:
const solution = (n, arr) => {
const counter = new Array(n).fill(0);
let max = 0, counterMaxed = false;
for (let curr of arr) {
if (curr > n) {
if (!counterMaxed) { counter.fill(max); counterMaxed = true; }
continue;
}
curr--; counter[curr]++; counterMaxed = false;
if (counter[curr] > max) { max = counter[curr]; }
}
return counter;
};
This gets a straight 100% score:
https://app.codility.com/demo/results/training3H48RM-6EG/