Created
December 1, 2015 07:23
-
-
Save divmgl/7375c0ed9c21dcbbf48b to your computer and use it in GitHub Desktop.
MaxCounters Javascript Solution 100%/100%
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
function solution(N, A) { | |
var M = A.length; // Length of the entry array | |
var C = []; // Counters | |
var H = 0; // Highest counter | |
var PH = 0; // Previously recorded highest counter | |
for(K = 0; K < N; K++) { // Initialize the array | |
C[K] = 0; | |
} | |
// If you're having trouble understanding the problem, here's an | |
// explanation. The array you are receiving has instructions as | |
// to how perform mutations on an existing array. For instance, | |
// if the first element of the array is 3, that means you need | |
// to increment the third counter by 1 (C[3] + 1). Your array | |
// would then look like [0, 0, 1, 0, 0]. Technically, we don't need | |
// N, but there is another rule where if the array element is | |
// equal to N + 1 then your counters will need to set to the | |
// highest counter value. | |
for(K = 0; K < M; K++) { // Iterate through the array (M = A.length) | |
// If the element is not N + 1, we need to increase a specific counter | |
if (A[K] !== N + 1) { | |
// Increase the counter designated. We will need to subtract 1 | |
// because arrays start at 0, not 1. | |
C[A[K] - 1]++; | |
// Let's keep track of the highest counter we have reached and | |
// assign it to the variable H. | |
if (H < C[A[K] - 1]) H = C[A[K] - 1]; | |
continue; | |
} | |
// This is an optimization. Basically, in large arrays with huge | |
// amounts of max counters, you will be performing O(N + M) operations | |
// constantly because you will need to assign every counter to the | |
// maximum over and over. We can solve this problem by keeping track | |
// of the previous maximum counter and if it changes, then we know we | |
// need to iterate through the counters and set the maximum. | |
if (H === PH) continue; | |
// Iterate through the counters and assign the maximum. This operation is | |
// O(N + M), so we need to make sure to call this the least amount possible. | |
// If we've reached this point, we can be sure that it's a maximum counter | |
// operation. | |
for(J = 0; J < N; J++) C[J] = PH = H; | |
} | |
// Return the counters | |
return C; | |
} |
// initialize all counters to 0
let counters = Array(N).fill(0)// The maximum value of the counter is 0 let max = 0 // This variable will determine if an increment all operation has been encountered // and its value determines the maximum increment all operation encountered so far // for start it is 0, and we will set it to the value of max when A[i] == N + 1 let max_all = 0 for(let i = 0; i < A.length; i++) { if(A[i] <= counters.length) { // if the value of A[i] is 1, we have to increment c[0] // and hence the following index const c_index = A[i] - 1 // if max all operation was found previously, // we have to set it here, because we are not setting anything in the else section // we are just setting a flag in the else section // if its value however is greater than max_all, it probably was already maxed // and later incremented, therefore we will skip it if(counters[c_index] < max_all) counters[c_index] = max_all // do the increment here const v = ++counters[c_index] // update the max if the current value is max max = v > max ? v : max } // this is straight forward else max_all = max } // if there are remaining items that have not been set to max_all inside the loop // we will update them here. // and we are updating them here instead of inside the for loop in the else section // to make the running time better. If updated inside the loop, we will have a running time of M * N // however here it's something like (M + N) ~ O(N) if(max_all) counters = counters.map(v => v < max_all ? max_all : v) // return the counters return counters
❤️
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
A 100% scoring solution in javascript