EquiLeader Solution
Task
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] = 2we 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] = 2the 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].
Solution
The first thing to note is that if a value is the leader of both subsequence, then it must be the leader of the array A.
So we first need to find this value by getting the ‘leader’ of A.
In order to calculate the leader of A, we use the hack described in Codility’s documentation:
This involves iterating over the array keeping a stack with any different values cancelling each other out. Any leader will be the remaining value in the stack. However any remaining value is not guaranteed to be a leader, so we still have to check with another iteration through the array.
If a leader of A is found, we can check that it is the leader of any subsequence by using partial sums (PrefixSums) of the frequency of the value.
The code is below:
int solution(vector<int> &A) {
size_t size = A.size();
// get leader of whole thing
int stackSize = 0;
int stackVal = -1;
for (size_t i = 0; i < size; i++) {
int val = A[i];
if (stackSize == 0) {
stackVal = val;
stackSize = 1;
} else {
if (val == stackVal) {
stackSize++;
} else {
stackSize–;
}
} // if (stackSize == 0)
} // for
// if stackSize>0, stackval = possible ‘leader’
if (stackSize > 0) {
int count = 0;
vector<int> partial(size);
for (size_t i = 0; i < size; i++) {
if (A[i] == stackVal)
count++;
partial[i] = count;
}
if (count > (size / 2)) {
// leader found
// count results
int res = 0;
for (size_t i = 1; i < size; i++) {
if ((partial[i – 1] > (i / 2)) && ((count – partial[i – 1]) > ((size – i) / 2))) {
res++;
}
}
return res;
} else {
return 0;
}
} else {
return 0;
}
}Test Function
This code tests the solution
int main() {
vector<int> A{4, 3, 4, 4, 4, 2};
assert(solution(A) == 2);
vector<int> A2{-1000000000, 2, 3, 4, 5, 6, 7, 1000000000};
assert(solution(A2) == 0);
}Results
| Correctness | 100% |
| Performance | 100% |
| Time Complexity | O(N) |