Dominator at app.codility.com/programmers in C++ 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
int solution(vector<int> &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 new vector in the lesson has been replaced here with a stack.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 vector, 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 pushed in (at top). Whenever the stack is empty during the iteration, a copy of the next value in the given vector, 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):#include <iostream>The output is 7, which is one of the expected indexes. The case of an empty given vector (N==0) was taken into consideration, at the beginning of the solution() function.
#include<stack>
#include<vector>
using namespace std;
int solution(vector<int> &A) {
int N = A.size();
if (N == 0)
return -1;
stack<int> st;
for (int i=0; i<N; i++) {
if (st.size() > 0) {
if (A[i] == st.top()) {
st.push(A[i]);
}
else {
st.pop();
}
}
else { //stack is empty
st.push(A[i]);
}
}
int candidate = -1;
if (st.size() > 0)
candidate = st.top();
int count = 0;
int indx = -1;
for (int i=0; i<N; i++) {
if (A[i] == candidate) {
count += 1;
indx = i;
}
}
if (count > N/2)
return indx;
else
return -1;
}
int main()
{
vector<int> P = {3, 4, 3, 2, 3, -1, 3, 3};
int ret = solution(P);
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*log(N)) or O(N)