Lesson 6: EquiLeader (Equi Leader)

Lesson 6: EquiLeaderhttps://codility.com/programmers/lessons/6

As my solution utilizes the O(N) algorithm to find a leader described in the reading material that Codility provides, so first read it briefly.
Open reading material (PDF)


The definition of `equi leader' is given as below in the problem.

``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.''

So let's think of this. 

Assume the value X is the leader of the whole array A and the total number of its occurrence is cntX. 

Now we have the value Y and the total number of its occurrence is cntY. The value Y can be any value other than X.

Since X is the leader, it can be said that cntX > N / 2. 

Then, it is always cntY < N / 2, since cntX + cntY <= N (because cntX > N / 2)

Since cntX > N / 2 and N / 2 > cntY, we can say cntX > cntY

The question is if this value Y can have an equi leader. The answer is NO, which means ``The leaders of the same value that makes an equip leader is always the leader of the whole array''.

Why? Assume that the value Y can have an equi leader at the index S.

This means, for A[0], A[1], ...., A[S], Y occurs more than X.

Suppose the number of occurrences of X and Y on the left side of the array divided by the index S are cntX_L, cntY_L respectively.

Then for A[n] (n <= S), 

it must be cntY_L > cntX_L  as Y is supposed to occur more than X to become the leader on the left side of the array divided at the index S.

Now let's think if Y can be also a leader of the right side of the array divided by the index S.

The total number of the occurrences of X and Y on the right side is cntX - cntX_L and cntY - cntY_L respectively.

so if the Y can also become the leader of the right side, it has to be cntX - cntX_L < cntY - cntY_L.

However, the assumption above leads to a contradiction.

cntX - cntX_L < cntY - cntY_L

This obviously contradicts since we assumed 

cntX   > cntY

cntX_L < cntY_L

This can only result as below.

cntX - cntX_L > cntY - cntY_L


This means that only the leader of the whole array can have an equi leader. 


Based on this condition, to solve this problem, we first find the leader of the whole array. If there is no leader, there won't be no equal leader. So just return 0.

After finding a leader (if any), we then scan the whole array again,  counting the occurrence of the leader at the current scanning position, comparing if the position can be an equi leader or not.
If we find a new equi leader, we increment the counter for the answer.

This strategy will result in the 100% score as below.

#include <alloca.h>

int solution(int A[], int N) {
    
    //first find the leader and count its occurances.
    //as all the values on the stack will be the same,
    //we only have to keep one value.
    int sp = 0;
    int candidate = 0;
    
    int i;
    for (i = 0; i < N; i++){
        if (sp == 0){
            sp++;
            candidate = A[i];
            continue;
        }
        
        if (candidate == A[i]){
            sp++;
        }
        else {
            sp--;
        }
    }
    
    //if there is no leader, there is no equi leader.
    if (sp == 0){
        return 0;
    }
    
    //now we check if the candidate value is really a leader
    int cnt = 0;
    for (i = 0; i < N; i++){
        if (A[i] == candidate){
            cnt++;
        }
    }
    
    //if there is no leader, there is no equi leader.
    if (cnt <= N / 2){
        return 0;
    }
    
    //now we have a leader.
    int leader = candidate;
  
    
    //let's count the number of equi leader.
    int lcnt = 0; //leader appeard until the index.
    int ans  = 0; //the number of equi leaders.
    for (i = 0; i < N; i++){
        if (A[i] == leader){
            lcnt++;
        }
        //check if the current index is a equi leader
        int lelems = i + 1;
        if ((lcnt > lelems / 2) && 
            ((cnt - lcnt) > (N - lelems) / 2)){
            ans++;
        }
    }
    
    return ans;
}