Dominator at app.codility.com/programmers in JavaScript Explained: Find an index of an array such that its value occurs at more than half of indices in the array.
Task score : 100% - Correctness : 100% ; Performance : 100%
Detected time complexity : O(N*log(N)) or 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
An array A consisting of N integers is given. The dominator of array A is the value that occurs in more than half of the elements of A.For example, consider array A such that
A[0] = 3 A[1] = 4 A[2] = 3
A[3] = 2 A[4] = 3 A[5] = -1
A[6] = 3 A[7] = 3
The dominator of A is 3 because it occurs in 5 out of 8 elements of A (namely in those with indices 0, 2, 4, 6 and 7) and 5 is more than a half of 8.
Write a function
function solution(A);
that, given an array A consisting of N integers, returns index of any element of array A in which the dominator of A occurs. The function should return -1 if array A does not have a dominator.
For example, given array A such that
A[0] = 3 A[1] = 4 A[2] = 3
A[3] = 2 A[4] = 3 A[5] = -1
A[6] = 3 A[7] = 3
the function may return 0, 2, 4, 6 or 7, as explained above.
Write an efficient algorithm for the following assumptions:
• N is an integer within the range [0..100,000];
• each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
Strategy:
The lesson for this problem is on leader. Here, dominator means leader. The reader should have read the lesson before coming here. The O(n+n) algorithm in the lesson (tutorial) should be envisaged here.The first O(n) time is for elimination of pairs of different values. The second O(n) verifies if the candidate is the dominator and also looks for an index expected. The reader should not confuse between Dominator, here, and Denominator elsewhere.
The pairs of different values are eliminated as follows: If the value that is at the top of the stack is different from the value that is to come next from the given array, then the value at the top of the stack is popped off and the iteration continues. Else the same value as what is in the stack (at the top) is unshifted in (at top). Whenever the stack is empty during the iteration, a copy of the next value in the given array, is copied into the stack. Any value remaining in the stack at the end of the iteration, is a candidate. There can be more than one of the same value remaining in the stack at the end of the iteration. If at the end of the iteration the stack is empty, then there is no candidate and so no dominator.
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;
if (N == 0)
return -1;
const st = []; //stack
for (let i=0; i<N; i++) {
if (st.length > 0) {
if (A[i] == st[0]) {
st.unshift(A[i]);
}
else {
st.shift;
}
}
else { //stack is empty
st.unshift(A[i]);
}
}
let candidate = -1;
if (st.length > 0)
candidate = st[0];
let count = 0;
let indx = -1;
for (let i=0; i<N; i++) {
if (A[i] == candidate) {
count += 1;
indx = i;
}
}
if (count > N/2)
return indx;
else
return -1;
}
const P = [3, 4, 3, 2, 3, -1, 3, 3];
let ret = solution(P);
document.write(ret + '<br>');
</script>
The output is 7, which is one of the expected indexes. The case of an empty given array (N==0) was taken into consideration, at the beginning of the solution() function.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*log(N)) or O(N)