EquiLeader

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].

#include <unordered_map>

int solution(vector<int> &A) {
    // write your code in C++11 (g++ 4.8.2)
    // Find the dominant element
    if (A.size() < 2) return 0;
    
    unordered_map<int, int> um;
    int dominant_num = 0;
    int dominant = A[0];
    for (auto i: A) {
        if (um.find(i) != um.end()) {
            um[i]++;
            if (dominant_num < um[i]) {
                dominant = i;
                dominant_num = um[i];
            }
            
            if (dominant_num >= int(A.size()) / 2 + 1) break;
        } else {
            um[i] = 1;
        }
    }
    
    if (dominant_num < int(A.size()) / 2 + 1) return 0;
    
    vector<int> presum;
    int s = 0;
    
    for (auto i: A) {
        if (i == dominant) s++;
        presum.push_back(s);
    }
    
    int output = 0;
    int size = int(A.size());
    for (int i = 0; i < size; i++) {
        if ((presum[i] > (i + 1) / 2) && (presum[size - 1] - presum[i] > (size - i - 1) / 2)) {
            output++;    
        }
    }
    
    return output;
    
}