EquiLeader
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.
Solution
#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; }