EquiLeader at app.codility.com/programmers in PHP 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):

<?php
function solution($A) {
    $N = count($A);
    $stck = new SplStack();    //stack
   
    for($i=0; $i < count($A); $i++) {
        if(count($stck) == 0) {
            $stck->push($A[$i]);
        }
        else {
            if($stck[0] == $A[$i]) {
                $stck->push($A[$i]);
            }
            else {
                $stck->pop();
            }
        }
    }
    
    if(count($stck) == 0)  //no candidate if stack is empty
        return 0;
        
    $candidate = $stck[0];
    $noLeaders = 0;
    for($i=0; $i < $N; $i++) {
      if($A[$i] == $candidate) {
            $noLeaders++;
        }
    }

    if($noLeaders <= (int)($N/2)) //there is no overall leader
        return 0;
    $leader = $candidate;

    $noleftLeaders = 0;
    $counter = 0;
    
    for($i=0; $i < count($A); $i++){
        if ($A[$i] == $leader) 
            $noleftLeaders++;
        $leftNoElements = $i+1;    //because of zero based indexing
        $rightNoElements = $N-1-$i;    //because of zero based indexing
        if (($noleftLeaders > (int)($leftNoElements/2))&&($noLeaders-$noleftLeaders > (int)($rightNoElements/2)))  //if leader is (sub) leader on both sides
            $counter++;
    }    
   
    return $counter;
}

$B = [4, 3, 4, 4, 4, 2];

$ret = solution($B);

echo $ret . "\n";
?>

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)

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

Cousins

BACK

Broad Network

Series Articles

EquiLeader at app.codility.com/programmers in PHP 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

Problem

Note:

Strategy

Smart Solution

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

Cousins

Comments

Series Articles

EquiLeader at app.codility.com/programmers in PHP 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

Problem

Note:

Strategy

Smart Solution

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

Cousins

Comments

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.