Straight Developer

In this article I am going to share with you a javascript solution to the second exercise of the leaders lessons part of codility lessons, the solution gets 100% score in matter of correctness and performance and has a time complexity of O(N)

EquiLeader task description on Codility:

Find the index S such that the leaders of the sequences A[0], A[1], …, A[S] and A[S + 1], A[S + 2], …, A[N – 1] are the same.

A non-empty array A consisting of N integers is given.

The leader of this array is the value that occurs in more than half of the elements of A.

An equi leader is an index S such that 0 ≤ S < N − 1 and two sequences A[0], A[1], …, A[S] and A[S + 1], A[S + 2], …, A[N − 1] have leaders of the same value.

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

we can find two equi leaders:

• 0, because sequences: (4) and (3, 4, 4, 4, 2) have the same leader, whose value is 4.
• 2, because sequences: (4, 3, 4) and (4, 4, 2) have the same leader, whose value is 4.

The goal is to count the number of equi leaders.

Write a function:

function solution(A);

that, given a non-empty array A consisting of N integers, returns the number of equi leaders.

For example, given: A[0] = 4 A[1] = 3 A[2] = 4 A[3] = 4 A[4] = 4 A[5] = 2

the function should return 2, as explained above.

Write an efficient algorithm for the following assumptions:

• N is an integer within the range [1..100,000];
• each element of array A is an integer within the range [−1,000,000,000..1,000,000,000].

Looping from right then from left

In order to determine if a specific index of the main array A is an “equi leader” or not we must:
-know what’s the leader of the subsequence that ends with the index in question
-know what’s the leader of the other subsequence (from the index until the end of the array)
if we have both of these information, all we need to do is to compare between the leader of the left subsequence and the leader of the right one and we’re able to say if an index is an equiLeader.
In order to do so, first we need to calculate the leader of each index of the array starting from the right, the first loop in my solution fills the leaders array giving us the leader of all the possible subsequences from the right. after that comes the second loop, this does the same thing but it goes from the left, at the same time it checks if an element is an equi leader or not and increments a counter each time it finds one,
at the end the counter will have exactly the number of equi leaders on A.

function solution(A) {
    var rightCounters=[]
    var leftCounters=[]
    var leaders=[]
    for(var i=A.length-1;i>=0;i--){
        var current=A[i]
        if(typeof rightCounters[current]=="undefined"){
            rightCounters[current]=1
        }
        else
            rightCounters[current]++
            if(rightCounters[current]>(A.length-i)/2)
            leaders[i]=current
            else{
                if(i!=A.length-1 && rightCounters[leaders[i+1]]>(A.length-i)/2)
                    leaders[i]=leaders[i+1]
                else
                    leaders[i]=-1
            }
    }
    var counter=0;
    var lastLeader=A[0]
    for(var i=0;i<A.length;i++){
        var current=A[i]
        if(typeof leftCounters[current]=="undefined")
            leftCounters[current]=1
        else
            leftCounters[current]++
        if(leftCounters[current]>(i+1)/2){
            if(current==leaders[i+1])
                counter++
            lastLeader=current;

        }
            else{
                if(lastLeader!=-1 && leftCounters[lastLeader]>(i+1)/2){
                    if(lastLeader==leaders[i+1])
                        counter++
                }
                else
                    lastLeader=-1
            }
        }
        return counter;
}

Do you have a solution that has a score of 100% and contains less lines of code? if so then don’t hesitate to share it with me in the comments below !