Tasks Details
easy
1.
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.
Task Score
100%
Correctness
100%
Performance
100%
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:
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] = 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].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used JavaScript
Time spent on task 8 minutes
Notes
not defined yet
Task timeline
Code: 01:41:34 UTC,
js,
verify,
result: Passed
// We can reason that to split the array and have two identical leaders, it must be the same leader for the whole array - so our first step is to calculate that leader. This has two steps, first we decide a candiate for the leader (ie. the number that occurs most often) and then we count the number of occurances to see if it is more than half. To find the candidate we can sort and pick the middle number or we can repeatedly remove pairs of unmatched numbers, whatever is left is the most frequently occuring number, we can do this using a stack. To find the equi leader we can again loop through the array but this time, using the index as the pivot, we compare the number of leaders each side of it, increasing our equi leader count if the correct conditions are met
function solution(A) {
let leader = null
let stackSize = 0
for (let i = 0; i < A.length; ++i) {
if (stackSize === 0) {
// empty stack store the value
leader = A[i]
stackSize++
} else {
// compare the value against that in the stack and add if same or decrease if different
if (A[i] === leader) {
stackSize++
} else {
stackSize--
}
}
}
// we need a count of leaders
let leaderCount = A.reduce((sum,elem) => {
return elem === leader ? sum + 1 : sum
}, 0 )
console.log('leader', leader, 'leaderCount', leaderCount)
// do we have a leader? if not then no need to continue
if ( leaderCount <= A.length / 2 ) return 0
let equiLeaders = 0
let leaderOccurances = 0
for (let s = 0; s < A.length; ++s) {
if (A[s] === leader) {
leaderOccurances++
let remainingLeaders = leaderCount - leaderOccurances
let remainingLength = A.length - s - 1
console.log('s', s,'leaderOccurances', leaderOccurances, 'remainingLeaders', remainingLeaders)
if ( leaderOccurances > s/2 && remainingLeaders > remainingLength/2 ) {
equiLeaders++
}
}
}
return equiLeaders
}
User test case 1:
[0, 0]
User test case 2:
[1, 2, 1, 1, 2, 1]
Analysis
expand all
Example tests
1.
0.143 s
OK
stdout:
leader 4 leaderCount 4 s 0 leaderOccurances 1 remainingLeaders 3 s 2 leaderOccurances 2 remainingLeaders 2 s 3 leaderOccurances 3 remainingLeaders 1 s 4 leaderOccurances 4 remainingLeaders 0
expand all
User tests
1.
0.141 s
OK
function result: 1
function result: 1
stdout:
leader 0 leaderCount 2 s 0 leaderOccurances 1 remainingLeaders 1 s 1 leaderOccurances 2 remainingLeaders 0
1.
0.141 s
OK
function result: 2
function result: 2
stdout:
leader 1 leaderCount 4 s 0 leaderOccurances 1 remainingLeaders 3 s 2 leaderOccurances 2 remainingLeaders 2 s 3 leaderOccurances 3 remainingLeaders 1 s 5 leaderOccurances 4 remainingLeaders 0
Code: 01:42:51 UTC,
js,
verify,
result: Passed
// We can reason that to split the array and have two identical leaders, it must be the same leader for the whole array - so our first step is to calculate that leader. This has two steps, first we decide a candiate for the leader (ie. the number that occurs most often) and then we count the number of occurances to see if it is more than half. To find the candidate we can sort and pick the middle number or we can repeatedly remove pairs of unmatched numbers, whatever is left is the most frequently occuring number, we can do this using a stack. To find the equi leader we can again loop through the array but this time, using the index as the pivot, we compare the number of leaders each side of it, increasing our equi leader count if the correct conditions are met
function solution(A) {
let leader = null
let stackSize = 0
for (let i = 0; i < A.length; ++i) {
if (stackSize === 0) {
// empty stack store the value
leader = A[i]
stackSize++
} else {
// compare the value against that in the stack and add if same or decrease if different
if (A[i] === leader) {
stackSize++
} else {
stackSize--
}
}
}
// we need a count of leaders
let leaderCount = A.reduce((sum,elem) => {
return elem === leader ? sum + 1 : sum
}, 0 )
console.log('leader', leader, 'leaderCount', leaderCount)
// do we have a leader? if not then no need to continue
if ( leaderCount <= A.length / 2 ) return 0
let equiLeaders = 0
let leaderOccurances = 0
for (let s = 0; s < A.length; ++s) {
if (A[s] === leader) {
leaderOccurances++
let remainingLeaders = leaderCount - leaderOccurances
let remainingLength = A.length - s - 1
console.log('s', s,'leaderOccurances', leaderOccurances, 'remainingLeaders', remainingLeaders, 'remainingLength', remainingLength)
if ( leaderOccurances > s/2 && remainingLeaders > remainingLength/2 ) {
console.log('equiLeaders', equiLeaders)
equiLeaders++
}
}
}
return equiLeaders
}
User test case 1:
[0, 0]
User test case 2:
[1, 2, 1, 1, 2, 1]
Analysis
expand all
Example tests
1.
0.136 s
OK
stdout:
leader 4 leaderCount 4 s 0 leaderOccurances 1 remainingLeaders 3 remainingLength 5 equiLeaders 0 s 2 leaderOccurances 2 remainingLeaders 2 remainingLength 3 equiLeaders 1 s 3 leaderOccurances 3 remainingLeaders 1 remainingLength 2 s 4 leaderOccurances 4 remainingLeaders 0 remainingLength 1
expand all
User tests
1.
0.133 s
OK
function result: 1
function result: 1
stdout:
leader 0 leaderCount 2 s 0 leaderOccurances 1 remainingLeaders 1 remainingLength 1 equiLeaders 0 s 1 leaderOccurances 2 remainingLeaders 0 remainingLength 0
1.
0.135 s
OK
function result: 2
function result: 2
stdout:
leader 1 leaderCount 4 s 0 leaderOccurances 1 remainingLeaders 3 remainingLength 5 equiLeaders 0 s 2 leaderOccurances 2 remainingLeaders 2 remainingLength 3 equiLeaders 1 s 3 leaderOccurances 3 remainingLeaders 1 remainingLength 2 s 5 leaderOccurances 4 remainingLeaders 0 remainingLength 0
Code: 01:43:08 UTC,
js,
verify,
result: Passed
// We can reason that to split the array and have two identical leaders, it must be the same leader for the whole array - so our first step is to calculate that leader. This has two steps, first we decide a candiate for the leader (ie. the number that occurs most often) and then we count the number of occurances to see if it is more than half. To find the candidate we can sort and pick the middle number or we can repeatedly remove pairs of unmatched numbers, whatever is left is the most frequently occuring number, we can do this using a stack. To find the equi leader we can again loop through the array but this time, using the index as the pivot, we compare the number of leaders each side of it, increasing our equi leader count if the correct conditions are met
function solution(A) {
let leader = null
let stackSize = 0
for (let i = 0; i < A.length; ++i) {
if (stackSize === 0) {
// empty stack store the value
leader = A[i]
stackSize++
} else {
// compare the value against that in the stack and add if same or decrease if different
if (A[i] === leader) {
stackSize++
} else {
stackSize--
}
}
}
// we need a count of leaders
let leaderCount = A.reduce((sum,elem) => {
return elem === leader ? sum + 1 : sum
}, 0 )
console.log('leader', leader, 'leaderCount', leaderCount)
// do we have a leader? if not then no need to continue
if ( leaderCount <= A.length / 2 ) return 0
let equiLeaders = 0
let leaderOccurances = 0
for (let s = 0; s < A.length; ++s) {
if (A[s] === leader) {
leaderOccurances++
let remainingLeaders = leaderCount - leaderOccurances
let remainingLength = A.length - s - 1
console.log('s', s,'leaderOccurances', leaderOccurances, 'remainingLeaders', remainingLeaders, 'remainingLength', remainingLength)
if ( leaderOccurances > s/2 && remainingLeaders > remainingLength/2 ) {
equiLeaders++
console.log('equiLeaders', equiLeaders)
}
}
}
return equiLeaders
}
User test case 1:
[0, 0]
User test case 2:
[1, 2, 1, 1, 2, 1]
Analysis
expand all
Example tests
1.
0.139 s
OK
stdout:
leader 4 leaderCount 4 s 0 leaderOccurances 1 remainingLeaders 3 remainingLength 5 equiLeaders 1 s 2 leaderOccurances 2 remainingLeaders 2 remainingLength 3 equiLeaders 2 s 3 leaderOccurances 3 remainingLeaders 1 remainingLength 2 s 4 leaderOccurances 4 remainingLeaders 0 remainingLength 1
expand all
User tests
1.
0.141 s
OK
function result: 1
function result: 1
stdout:
leader 0 leaderCount 2 s 0 leaderOccurances 1 remainingLeaders 1 remainingLength 1 equiLeaders 1 s 1 leaderOccurances 2 remainingLeaders 0 remainingLength 0
1.
0.136 s
OK
function result: 2
function result: 2
stdout:
leader 1 leaderCount 4 s 0 leaderOccurances 1 remainingLeaders 3 remainingLength 5 equiLeaders 1 s 2 leaderOccurances 2 remainingLeaders 2 remainingLength 3 equiLeaders 2 s 3 leaderOccurances 3 remainingLeaders 1 remainingLength 2 s 5 leaderOccurances 4 remainingLeaders 0 remainingLength 0
Code: 01:44:08 UTC,
js,
verify,
result: Failed
// We can reason that to split the array and have two identical leaders, it must be the same leader for the whole array - so our first step is to calculate that leader. This has two steps, first we decide a candiate for the leader (ie. the number that occurs most often) and then we count the number of occurances to see if it is more than half. To find the candidate we can sort and pick the middle number or we can repeatedly remove pairs of unmatched numbers, whatever is left is the most frequently occuring number, we can do this using a stack. To find the equi leader we can again loop through the array but this time, using the index as the pivot, we compare the number of leaders each side of it, increasing our equi leader count if the correct conditions are met
function solution(A) {
let leader = null
let stackSize = 0
for (let i = 0; i < A.length; ++i) {
if (stackSize === 0) {
// empty stack store the value
leader = A[i]
stackSize++
} else {
// compare the value against that in the stack and add if same or decrease if different
if (A[i] === leader) {
stackSize++
} else {
stackSize--
}
}
}
// we need a count of leaders
let leaderCount = A.reduce((sum,elem) => {
return elem === leader ? sum + 1 : sum
}, 0 )
console.log('leader', leader, 'leaderCount', leaderCount)
// do we have a leader? if not then no need to continue
if ( leaderCount <= A.length / 2 ) return 0
let equiLeaders = 0
let leaderOccurances = 0
for (let s = 0; s < A.length; ++s) {
if (A[s] === leader) {
leaderOccurances++
}
let remainingLeaders = leaderCount - leaderOccurances
let remainingLength = A.length - s - 1
console.log('s', s,'leaderOccurances', leaderOccurances, 'remainingLeaders', remainingLeaders, 'remainingLength', remainingLength)
if ( leaderOccurances > s/2 && remainingLeaders > remainingLength/2 ) {
equiLeaders++
console.log('equiLeaders', equiLeaders)
}
}
return equiLeaders
}
User test case 1:
[0, 0]
User test case 2:
[1, 2, 1, 1, 2, 1]
Analysis
expand all
Example tests
1.
0.133 s
WRONG ANSWER,
got 3 expected 2
stdout:
leader 4 leaderCount 4 s 0 leaderOccurances 1 remainingLeaders 3 remainingLength 5 equiLeaders 1 s 1 leaderOccurances 1 remainingLeaders 3 remainingLength 4 equiLeaders 2 s 2 leaderOccurances 2 remainingLeaders 2 remainingLength 3 equiLeaders 3 s 3 leaderOccurances 3 remainingLeaders 1 remainingLength 2 s 4 leaderOccurances 4 remainingLeaders 0 remainingLength 1 s 5 leaderOccurances 4 remainingLeaders 0 remainingLength 0
expand all
User tests
1.
0.135 s
OK
function result: 1
function result: 1
stdout:
leader 0 leaderCount 2 s 0 leaderOccurances 1 remainingLeaders 1 remainingLength 1 equiLeaders 1 s 1 leaderOccurances 2 remainingLeaders 0 remainingLength 0
1.
0.133 s
OK
function result: 4
function result: 4
stdout:
leader 1 leaderCount 4 s 0 leaderOccurances 1 remainingLeaders 3 remainingLength 5 equiLeaders 1 s 1 leaderOccurances 1 remainingLeaders 3 remainingLength 4 equiLeaders 2 s 2 leaderOccurances 2 remainingLeaders 2 remainingLength 3 equiLeaders 3 s 3 leaderOccurances 3 remainingLeaders 1 remainingLength 2 s 4 leaderOccurances 3 remainingLeaders 1 remainingLength 1 equiLeaders 4 s 5 leaderOccurances 4 remainingLeaders 0 remainingLength 0
Code: 01:46:23 UTC,
js,
verify,
result: Passed
// We can reason that to split the array and have two identical leaders, it must be the same leader for the whole array - so our first step is to calculate that leader. This has two steps, first we decide a candiate for the leader (ie. the number that occurs most often) and then we count the number of occurances to see if it is more than half. To find the candidate we can sort and pick the middle number or we can repeatedly remove pairs of unmatched numbers, whatever is left is the most frequently occuring number, we can do this using a stack. To find the equi leader we can again loop through the array but this time, using the index as the pivot, we compare the number of leaders each side of it, increasing our equi leader count if the correct conditions are met
function solution(A) {
let leader = null
let stackSize = 0
for (let i = 0; i < A.length; ++i) {
if (stackSize === 0) {
// empty stack store the value
leader = A[i]
stackSize++
} else {
// compare the value against that in the stack and add if same or decrease if different
if (A[i] === leader) {
stackSize++
} else {
stackSize--
}
}
}
// we need a count of leaders
let leaderCount = A.reduce((sum,elem) => {
return elem === leader ? sum + 1 : sum
}, 0 )
console.log('leader', leader, 'leaderCount', leaderCount)
// do we have a leader? if not then no need to continue
if ( leaderCount <= A.length / 2 ) return 0
let equiLeaders = 0
let leaderOccurances = 0
for (let s = 0; s < A.length; ++s) {
if (A[s] === leader) {
leaderOccurances++
}
let remainingLeaders = leaderCount - leaderOccurances
let leftLength = s + 1
let rightLength = A.length - leftLength
console.log('leftLength', leftLength,'leaderOccurances', leaderOccurances, 'remainingLeaders', remainingLeaders, 'rightLength', rightLength)
if ( leaderOccurances > leftLength/2 && remainingLeaders > rightLength/2 ) {
equiLeaders++
console.log('equiLeaders', equiLeaders)
}
}
return equiLeaders
}
User test case 1:
[0, 0]
User test case 2:
[1, 2, 1, 1, 2, 1]
Analysis
expand all
Example tests
1.
0.141 s
OK
stdout:
leader 4 leaderCount 4 leftLength 1 leaderOccurances 1 remainingLeaders 3 rightLength 5 equiLeaders 1 leftLength 2 leaderOccurances 1 remainingLeaders 3 rightLength 4 leftLength 3 leaderOccurances 2 remainingLeaders 2 rightLength 3 equiLeaders 2 leftLength 4 leaderOccurances 3 remainingLeaders 1 rightLength 2 leftLength 5 leaderOccurances 4 remainingLeaders 0 rightLength 1 leftLength 6 leaderOccurances 4 remainingLeaders 0 rightLength 0
expand all
User tests
1.
0.134 s
OK
function result: 1
function result: 1
stdout:
leader 0 leaderCount 2 leftLength 1 leaderOccurances 1 remainingLeaders 1 rightLength 1 equiLeaders 1 leftLength 2 leaderOccurances 2 remainingLeaders 0 rightLength 0
1.
0.133 s
OK
function result: 3
function result: 3
stdout:
leader 1 leaderCount 4 leftLength 1 leaderOccurances 1 remainingLeaders 3 rightLength 5 equiLeaders 1 leftLength 2 leaderOccurances 1 remainingLeaders 3 rightLength 4 leftLength 3 leaderOccurances 2 remainingLeaders 2 rightLength 3 equiLeaders 2 leftLength 4 leaderOccurances 3 remainingLeaders 1 rightLength 2 leftLength 5 leaderOccurances 3 remainingLeaders 1 rightLength 1 equiLeaders 3 leftLength 6 leaderOccurances 4 remainingLeaders 0 rightLength 0
Code: 01:47:40 UTC,
js,
verify,
result: Passed
// We can reason that to split the array and have two identical leaders, it must be the same leader for the whole array - so our first step is to calculate that leader. This has two steps, first we decide a candiate for the leader (ie. the number that occurs most often) and then we count the number of occurances to see if it is more than half. To find the candidate we can sort and pick the middle number or we can repeatedly remove pairs of unmatched numbers, whatever is left is the most frequently occuring number, we can do this using a stack. To find the equi leader we can again loop through the array but this time, using the index as the pivot, we compare the number of leaders each side of it, increasing our equi leader count if the correct conditions are met
function solution(A) {
let leader = null
let stackSize = 0
for (let i = 0; i < A.length; ++i) {
if (stackSize === 0) {
// empty stack store the value
leader = A[i]
stackSize++
} else {
// compare the value against that in the stack and add if same or decrease if different
if (A[i] === leader) {
stackSize++
} else {
stackSize--
}
}
}
// we need a count of leaders
let leaderCount = A.reduce((sum,elem) => {
return elem === leader ? sum + 1 : sum
}, 0 )
// do we have a leader? if not then no need to continue
if ( leaderCount <= A.length / 2 ) return 0
let equiLeaders = 0
let leaderOccurances = 0
for (let s = 0; s < A.length; ++s) {
if (A[s] === leader) {
leaderOccurances++
}
let remainingLeaders = leaderCount - leaderOccurances
let leftLength = s + 1
let rightLength = A.length - leftLength
if ( leaderOccurances > leftLength/2 && remainingLeaders > rightLength/2 ) {
equiLeaders++
}
}
return equiLeaders
}
User test case 1:
[0, 0]
User test case 2:
[1, 2, 1, 1, 2, 1]
Analysis
Code: 01:47:53 UTC,
js,
verify,
result: Passed
// We can reason that to split the array and have two identical leaders, it must be the same leader for the whole array - so our first step is to calculate that leader. This has two steps, first we decide a candiate for the leader (ie. the number that occurs most often) and then we count the number of occurances to see if it is more than half. To find the candidate we can sort and pick the middle number or we can repeatedly remove pairs of unmatched numbers, whatever is left is the most frequently occuring number, we can do this using a stack. To find the equi leader we can again loop through the array but this time, using the index as the pivot, we compare the number of leaders each side of it, increasing our equi leader count if the correct conditions are met
function solution(A) {
let leader = null
let stackSize = 0
for (let i = 0; i < A.length; ++i) {
if (stackSize === 0) {
// empty stack store the value
leader = A[i]
stackSize++
} else {
// compare the value against that in the stack and add if same or decrease if different
if (A[i] === leader) {
stackSize++
} else {
stackSize--
}
}
}
// we need a count of leaders
let leaderCount = A.reduce((sum,elem) => {
return elem === leader ? sum + 1 : sum
}, 0 )
// do we have a leader? if not then no need to continue
if ( leaderCount <= A.length / 2 ) return 0
let equiLeaders = 0
let leaderOccurances = 0
for (let s = 0; s < A.length; ++s) {
if (A[s] === leader) {
leaderOccurances++
}
let remainingLeaders = leaderCount - leaderOccurances
let leftLength = s + 1
let rightLength = A.length - leftLength
if ( leaderOccurances > leftLength/2 && remainingLeaders > rightLength/2 ) {
equiLeaders++
}
}
return equiLeaders
}
User test case 1:
[0, 0]
User test case 2:
[1, 2, 1, 1, 2, 1]
Analysis
Code: 01:47:58 UTC,
js,
final,
score:
100
// We can reason that to split the array and have two identical leaders, it must be the same leader for the whole array - so our first step is to calculate that leader. This has two steps, first we decide a candiate for the leader (ie. the number that occurs most often) and then we count the number of occurances to see if it is more than half. To find the candidate we can sort and pick the middle number or we can repeatedly remove pairs of unmatched numbers, whatever is left is the most frequently occuring number, we can do this using a stack. To find the equi leader we can again loop through the array but this time, using the index as the pivot, we compare the number of leaders each side of it, increasing our equi leader count if the correct conditions are met
function solution(A) {
let leader = null
let stackSize = 0
for (let i = 0; i < A.length; ++i) {
if (stackSize === 0) {
// empty stack store the value
leader = A[i]
stackSize++
} else {
// compare the value against that in the stack and add if same or decrease if different
if (A[i] === leader) {
stackSize++
} else {
stackSize--
}
}
}
// we need a count of leaders
let leaderCount = A.reduce((sum,elem) => {
return elem === leader ? sum + 1 : sum
}, 0 )
// do we have a leader? if not then no need to continue
if ( leaderCount <= A.length / 2 ) return 0
let equiLeaders = 0
let leaderOccurances = 0
for (let s = 0; s < A.length; ++s) {
if (A[s] === leader) {
leaderOccurances++
}
let remainingLeaders = leaderCount - leaderOccurances
let leftLength = s + 1
let rightLength = A.length - leftLength
if ( leaderOccurances > leftLength/2 && remainingLeaders > rightLength/2 ) {
equiLeaders++
}
}
return equiLeaders
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.142 s
OK
2.
0.141 s
OK
3.
0.141 s
OK
1.
0.144 s
OK
2.
0.138 s
OK
3.
0.137 s
OK
1.
0.138 s
OK
2.
0.139 s
OK
1.
0.139 s
OK
1.
0.147 s
OK