Straight Developer

This is a 100% score solution in matter of correctness and performance for the first exercise of the leader lessons section on Codility.com, as I am a web developer I’ve used javascript in order to achieve this result.
Here’s the exercise description on Codility:

An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.

For example, consider array A such that A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3

The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.

Write a function

function solution(A);

that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return −1 if array A does not have a dominator.

For example, given array A such that A[0] = 3 A[1] = 4 A[2] = 3 A[3] = 2 A[4] = 3 A[5] = -1 A[6] = 3 A[7] = 3

the function may return 0, 2, 4, 6 or 7, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].

Using a counter for each number on the array

In order to find if a specific number is a dominant or not we need to count how much it occurs in the A array right? that means that we need some kind of a counter, but since there’s not one but many different numbers in the array then we’ll need as much counters as the distinct numbers of the array that’s why I created a counter in a form of an array and named it counters, the idea is to dedicate a cell for each of the array’s distinct numbers, so if we come across the number 3 for example then we’ll simply do the following:

counters[3]++

of course, this is in the case where we met 3 for the second time, otherwise we need to give the cell a default value before we increment it (we can’t increment an undefined variable)

if(typeof counters[3]==”undefined”)
counters[3]=1

when we loop on our main array A and calculate each distinct number occurrences we’ll end up with an array containing the counters of all those numbers but we’re still unable to tell which number is the dominant unless we create a second loop or use the max function to get which counter is the greater, this will work but will definitely cost us in performance leading to a lower result than 100% that’s why I am not looping on the counters or using the max (reduce) function in this solution. Instead, I simply check if one of the counter has reached the half+1 condition, if it is true, the loop stops and returns the current index of the number of which the counter is greater than half+1

if(counters[current]>A.length/2)
return i

Here’s the solution in full:

function solution(A) {
    var counters=[]
    for(var i=0;i<A.length;i++){
    var current=A[i];
        if(typeof counters[current]=="undefined")
        counters[current]=1
        else
        counters[current]++
        if(counters[current]>A.length/2)
        return i
        
    }
    return -1;
}