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(int A[], int N);
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 (problem) for this lesson, on Dominator (Leader).The problem states that an equi-leader results in two sub-ranges that complete the whole range of the given array.
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 array 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
A program with the solution function is as follows (read through the code and comments). Pay particular attention to the solution() function definition and to the user code in the main() function.#include <stdio.h>The output is 2 as expected in O(n+n+n) time. The push(), pop() and top() methods (functions) of the stack object, each takes O(1) time, and are ignored.
#include <stdlib.h>
struct Element {
int value;
struct Element *previous;
};
struct Stack {
int size;
struct Element *back;
int (*top)();
void (*push)(int);
void (*pop)();
} stack;
int top() {
if (stack.size > 0) //stack has at least 1 element
return stack.back->value; //use -> to obtain value from a pointer
else
printf("Error: No element to remove from stack!\n");
}
void push(int inte) {
struct Element *element = malloc(sizeof(struct Element)); //declaring and creating the object, element
if (element != 0) { //check whether allocation of memory element was successful
element->value = inte;
if (stack.size == 0) { //first element
element->previous = 0;
stack.back = element;
stack.size = stack.size + 1; //add 1 to size
}
else {
element->previous = stack.back; //previous points to previous element
stack.back = element; //stack points to new element
stack.size = stack.size + 1; //add 1 to size
}
}
else {
printf("Error: New element could not be created!\n");
exit(1);
}
}
void pop() {
if (stack.size > 0) { //stack has at least 1 element
struct Element *lastElement = stack.back;
stack.back = lastElement->previous; //point to previous element
free(lastElement); //free last (top) element from memory
stack.size = stack.size - 1; //subtract 1 from size
}
else {
printf("Error: No element to remove from stack!\n");
exit(1);
}
}
int solution(int A[], int N) {
int leader = -1000000001;
stack.push(A[0]);
// O(n) time
for (int i=1; i<N; i++) {
if (stack.size != 0 && stack.top() == A[i])
stack.push(A[i]);
else if (stack.size != 0) //stack top and in-coming are different
stack.pop();
else //stack is empty
stack.push(A[i]);
}
int candidate = -1000000001;
if (stack.size != 0)
candidate = stack.top();
else
leader = -1000000001;
int noLeaders = 0;
// Another O(n) time
for (int i=0; i<N; i++) {
if (A[i] == candidate)
noLeaders += 1;
if (noLeaders > N/2) {
leader = candidate;
break;
}
}
int noleftLeaders = 0;
int counter = 0;
if (leader != -1000000001) { //leader exists
for(unsigned int i=0;i<N;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(int argc, char **argv)
{
//Assigning stack attributes and methods (functions)
stack.size = 0;
stack.top = top;
stack.push = push;
stack.pop = pop;
//user code begins
int A[] = {4, 3, 4, 4, 4, 2};
int N = sizeof(A)/sizeof(A[0]); //divide size of array by size of one (first) element
int ret = solution(A, N);
printf("%i\n", ret);
//user code begins
return 0;
}
The "noLeaders-noleftLeaders" expression means " noRightLeaders".
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)