EquiLeader at app.codility.com/programmers in JavaScript 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:
function solution(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.This 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 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
The solution() function is in the following program (read the code and comments):
<script type='text/javascript'>
function solution(A) {
let N = A.length;
const stck = []; //stack
for(let i=0; i<A.length; i++) {
if(stck.length == 0) {
stck.unshift(A[i]);
}
else {
if(stck[0] == A[i]) {
stck.unshift(A[i]);
}
else {
stck.shift;
}
}
}
if(stck.length == 0) //no candidate if stack is empty
return 0;
let candidate = stck[0];
let noLeaders = 0;
for(let i=0; i<N; i++) {
if(A[i] == candidate) {
noLeaders++;
}
}
if(noLeaders <= parseInt(N/2)) //there is no overall leader
return 0;
let leader = candidate;
let noleftLeaders = 0;
let counter = 0;
for(let i=0;i<A.length;i++){
if (A[i] == leader)
noleftLeaders++;
let leftNoElements = i+1; //because of zero based indexing
let rightNoElements = N-1-i; //because of zero based indexing
if ((noleftLeaders > parseInt(leftNoElements/2))&&(noLeaders-noleftLeaders > parseInt(rightNoElements/2))) //if leader is (sub) leader on both sides
counter++;
}
return counter;
}
const B = [4, 3, 4, 4, 4, 2];
let ret = solution(B);
document.write(ret + '<br>');
</script>
The output is 2.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)