[Codility] Lesson 8 - EquiLeader

Task discription

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:

int solution(vector<int> &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].

Source code

#include <algorithm>
#include <map>

int solution(vector<int> &A) {
    int n = A.size();
    int ans = 0;
    int leader, max = 0;
    map<int, int> m; 

    if(n == 1){
        return 0;
    }

    // leader 구하기
    for(int i=0;i<n;i++){
        if(m.find(A[i]) != m.end()){
            m[A[i]] += 1; 
        }else{
            m.insert(pair<int, int>(A[i], 1));
        }
		
        if(max < m[A[i]]){
            max = m[A[i]]; // leader의 cnt수
            leader = A[i]; // leader
        }
    }
	
    // leader가 존재하지 않는 경우
    if(max < n/2) {
        return 0;
    }

    // 4 / 3 4 4 4 2 라면 leftCnt 1 RightCnt 3
    int leftCnt = 0;
    int rightCnt = max;
    for(int i=0;i<n;i++) {
        if(A[i] == leader) {
            leftCnt++;
            rightCnt--;
        }
        // 둘 다 leader인지 check
        if(leftCnt > (i+1)/2 && rightCnt > (n-i-1)/2) {
            ans++;
        }
    }

    return ans;
}

Review

Ref. https://mirae-kim.tistory.com/124