EquiLeader at app.codility.com/programmers in C++ Explained: 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.
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)
Lesson 8 at app.codility.com/programmers
The solution and its explanation are given below.
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 5 Jul 2025
Problem
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].
Note:
It is assumed that the reader has read the lesson, Leader, for this problem, and has done the previous test for this lesson, on Dominator.The problem states that an equi-leader results in two sub-ranges that complete the whole range of the given vector.
It is important to realize that for this problem, the leader for the whole range is the same leader for the two sub-ranges.
Strategy
- Look for a leader in O(n+n) time for the whole range, noting the total number of leaders, if a leader exists.- Re-scan the given vector in O(n) time, where each index is presumed to be an equi leader, S before being discarded, if it is not an equi leader. If the leader is a sub leader for any two sub-ranges, then the counter is incremented by 1.
Smart Solution
The solution() function is in the following program (read the code and comments):#include <iostream>The output is 2.
#include<stack>
#include<vector>
using namespace std;
int solution(vector<int> &A) {
int N = A.size();
stack<int> stck;
for(unsigned int i=0; i<A.size(); i++) {
if(stck.empty()) {
stck.push(A[i]);
}
else {
if(stck.top() == A[i]) {
stck.push(A[i]);
}
else {
stck.pop();
}
}
}
if(stck.empty()) //no candidate if stack is empty
return 0;
int candidate = stck.top();
int noLeaders = 0;
for(int i=0; i<N; i++) {
if(A[i] == candidate) {
noLeaders++;
}
}
if(noLeaders <= N/2) //there is no overall leader
return 0;
int leader = candidate;
int noleftLeaders = 0;
int counter = 0;
for(unsigned int i=0;i<A.size();i++){
if (A[i] == leader)
noleftLeaders++;
int leftNoElements = i+1; //because of zero based indexing
int rightNoElements = N-1-i; //because of zero based indexing
if ((noleftLeaders > leftNoElements/2)&&(noLeaders-noleftLeaders > rightNoElements/2)) //if leader is (sub) leader on both sides
counter++;
}
return counter;
}
int main()
{
vector<int> B{4, 3, 4, 4, 4, 2};
int ret = solution(B);
cout << ret <<'\n';
return 0;
}
At app.codility.com/programmers the scoring and detected time complexity for this solution() is:
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N)