Dominator at app.codility.com/programmers in PHP 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):
<?php
function solution($A) {
$N = count($A);
if ($N == 0)
return -1;
$st = new SplStack(); //stack
for ($i=0; $i < $N; $i++) {
if (count($st) > 0) {
if ($A[$i] == $st[0]) {
$st->push($A[$i]);
}
else {
$st->pop();
}
}
else { //stack is empty
$st->push($A[$i]);
}
}
$candidate = -1;
if (count($st) > 0)
$candidate = $st[0];
$count = 0;
$indx = -1;
for ($i=0; $i < $N; $i++) {
if ($A[$i] == $candidate) {
$count += 1;
$indx = $i;
}
}
if ($count > $N/2)
return $indx;
else
return -1;
}
$P = [3, 4, 3, 2, 3, -1, 3, 3];
$ret = solution($P);
echo $ret . "\n";
?>
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)
The rest of the 17 lessons, with explanation of lessons, explanation of tasks, and explanation of solutions, can be found at (click): Explanations in PHP for the 17 Algorithm Lessons at https://app.codility.com/programmers with Problems and Solutions
Related Links
Basics of PHP with Security ConsiderationsWhite Space in PHP
PHP Data Types with Security Considerations
PHP Variables with Security Considerations
PHP Operators with Security Considerations
PHP Control Structures with Security Considerations
PHP String with Security Considerations
PHP Arrays with Security Considerations
PHP Functions with Security Considerations
PHP Return Statement
Exception Handling in PHP
Variable Scope in PHP
Constant in PHP
PHP Classes and Objects
Reference in PHP
PHP Regular Expressions with Security Considerations
Date and Time in PHP with Security Considerations
Files and Directories with Security Considerations in PHP
Writing a PHP Command Line Tool
PHP Core Number Basics and Testing
Validating Input in PHP
PHP Eval Function and Security Risks
PHP Multi-Dimensional Array with Security Consideration
Mathematics Functions for Everybody in PHP
PHP Cheat Sheet and Prevention Explained
More Related Links