Leader for app.codility.com/programmers Explained in C++
Category of Article : Technology | Computers and Software | Algorithm
By: Chrysanthus Date Published: 5 Jul 2025
value occurs more than n/2 times.
|
Sequence |
a0 |
a1 |
a2 |
a2 |
a4 |
a5 |
a6 |
|
Elements |
6 |
8 |
4 |
6 |
8 |
6 |
6 |
|
Index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
In the table the leader is highlighted in gray. It is possible to have a list without any leader. Notice that the sequence can have at most one leader. This is because, if there are two or more leaders, none of such a supposed leader would occur more than n/2 times for the whole list. By definition, a leader occurs more than n/2 times for the whole list.
The leader may be found in different ways. Some methods are described in this lesson, starting with
trivially, slow ideas and ending with very creative, fast algorithms. The task is to find the value
of the leader of the sequence a0, a1 , . . . , an-1 , such that 0 <= ai <= 109 . If there is no leader,
the result should be -1.
The leader may be found in different ways. Some methods are described in this lesson, starting with
trivially, slow ideas and ending with very creative, fast algorithms. The task is to find the value
of the leader of the sequence a0, a1 , . . . , an-1 , such that 0 <= ai <= 109 . If there is no leader,
the result should be -1.
Note:
Leader occurring more than n/2 times refers to C++ integer division. With integer division, 7/2 = 3½ = 3 and 6/2 = 3. Similarly, 5/2 = 2½ = 2 and 4/2 = 2. Similarly, 9/2 = 4½ = 4 and 8/2 = 4; and so on. That is, once a value occurs more than the integer division of n/2 times, then that is the leader. Again, with integer division, 7/2 is 3 and not 3½; 5/2 is 2 and not 2½; 9/2 is 4 and not 4½; and so on.Solution with O(n2) Time Complexity
This uses two for-loops, with one nested in the other. The outer for-loop chooses an element. The inner for-loop runs through all the elements in the list, to see if the element chosen by the outer for-loop occurs more than n/2 times. The outer for-loop begins by choosing the first element, then the second element, then the third, until the last element. The program is:#include <iostream>The output is 6.
#include <vector>
using namespace std;
int slowLeader(vector<int> A) {
int n = A.size();
int leader = -1;
for (int i=0; i<n; i++) {
int candidate = A[i];
int count = 0;
for (int j=0; j<n; j++) {
if (A[j] == candidate)
count += 1;
if (count > n/2) {
leader = candidate;
break;
}
}
if (count > n/2)
break;
}
return leader;
}
int main(int argc, char **argv)
{
vector<int> A = {6, 8, 4, 6, 8 ,6, 6};
int ret = slowLeader(A);
cout << ret << endl;
return 0;
}
Why the break Instructions? - Imagine that the list has a leader and this leader value forms the first elements in the list, then as soon as it is detected, these for-loops should break-off avoiding unnecessary iterations, up to n2 times. However, the above for-loops constitute O(n2) times in time complexity parlance. The maximum possible number of iterations (operations) is always quoted for time complexity.
Solution with O(n.log(n) + n) time complexity
If the list is first sorted in n.log2n time, and if the list has a leader, then the leader value will occur at zero based index n/2 (integer division). Remember that the leader occurs in more than n/2 times (integer division). In the sorted list, the first element may not be the leader and the last element may also not be the leader. Also, sorting the list does not guarantee that the list has a leader.After sorting, the value at index n/2 is assumed to be the leader; it is the candidate. In an additional maximum of n operations, the whole list has to be scanned to see if the candidate occurs more than n/2 times (integer division), to confirm that it is a leader. The following fastLeader() function illustrates this with the above list:
#include <iostream>The output is 6. The C++ sort() function takes about n.log(n) time and the for-loop takes a maximum of n time (actually, not more than n/2 plus 1 time). The statements outside the for-loop of constant time, O(1) are not included in the determination of the overall time complexity. All the statements in the for-loop body, are together considered as one main operation.
#include <vector>
#include <algorithm>
using namespace std;
int fastLeader(vector<int> A) {
int n = A.size();
int leader = -1;
sort(A.begin(), A.end());
int candidate = A[n/2];
int count = 0;
for (int j=0; j<n; j++) {
if (A[j] == candidate)
count += 1;
if (count > n/2) {
leader = candidate;
break;
}
}
return leader;
}
The arguments for the C++ sort() function are the start of the vector and the end of the vector. This sort() function is in the algorithm library, which has to be included (imported) into the program.
Solution with O(n + n) Time Complexity
Consider the above given unsorted list again:6, 8, 4, 6, 8, 6, 6
Beginning from the first element (left), any next two elements that are not the same, are removed from the list. The two elements must not necessarily occur consecutively (see sorting example below). 6 and 8 above are not the same. If they are removed, the list will become:
4, 6, 8, 6, 6
From the left again, if 4 and 6 are removed, the list will become:
8 ,6, 6
From the left again, if 8 and 6 are removed, the list will become:
6
which is the leader for the above list. However, with some other lists, this would not necessarily be the leader. It might just be the majority element and not the absolute majority element (above n/2). So 6 here is the candidate. Going through the list like this, takes O(n) operations. Another O(n) operations are needed to see if the candidate is the absolute majority element and not just the majority element. In other words, the original list has to be scanned to see if the candidate occurs more than n/2 times (integer division).
The removing of pairs of different elements, in order to end at the candidate, can better be appreciated (learned) with the sorted list, though sorting is not involved in the algorithm, explained below.
Removing Pairs of Different Elements, seen with a Sorted List
The following is a sorted list, from above:4, 6, 6, 6, 6 ,8, 8
From the left, if 4 and 6 that are different are removed, the remaining list is:
6, 6, 6, 8, 8
The next two 6 's are the same; they are not removed.
If the last 6 and the first 8 (from the left) that are different are removed, the list becomes:
6, 6, 8
Removing the last 6 here and the remaining 8, leads to a remaining list of:
6
Note that the 6 and 8 removed are not consecutive elements originally.
Now, after removal of different pairs of elements, if one element is remaining, then that is either the
majority element or the absolute majority element. That is the candidate, and not necessarily the leader. In other words, that may be the majority element and not necessarily the absolute majority element (leader). If more than one element is remaining in the final reduced list, then such elements must be the same. If they are not the same, then pairs of different elements still have to be removed.
The final list may have one or more than one element of the same value. The value is the candidate. It might be just a majority element or it might actually be the leader (absolute majority element). Another O(n) operations still has to be performed to know if the candidate occurs more than n/2 times (integer division).
So the time complexity is O(n+n). There should be no sorting here. The first n is for the removal of pairs of different elements. The second n is for the verification, if the candidate is truly the leader.
In the following program of O(n+n) time complexity, the removing of elements is not achieved as bluntly as described above. Instead, a new vector object is created, with one element, which is the first element copied from the given vector. The rest of the elements of the given vector are sent (push_back) to the new vector, one-by-one.
As from the second element, copied and sent, each time sending is to occur, the next element to be stacked, is compared with the top element of the stack. If they are different, the top element in the stack are popped off and the in-coming element is not put into the stack. If they are the same, then nothing is removed from the stack. At the end of the scanning of the given array, there may be at least one element in the new vector. That element is the candidate. The candidate may be one or more of the same copies of the same value (in the new vector). If the size of the new vector ends as zero, then there is no leader. The states of the new vector is best illustrated with a sorted list, though no sorting is involved with the O(n+n) algorithm. The sorted list from above is:
4, 6, 6, 6, 6 ,8, 8
At the beginning, the new vector is:
4
When 6 is copied and added (at the back), the new vector becomes:
4, 6
The first and the last elements of the new vector are compared. They are not equal, and so the first and last elements of the new vector are removed (from the new vector). At this point, the new vector becomes empty. Next, 6 is copied for the new vector to have only 6. No comparison can be made at this stage, since the new vector now has only one element. So the fourth element at index 3 of the given vector, which is still 6, is copied, to the new vector. The state (content) of the new vector is now,
6, 6
Comparison of the first and last elements of the new vector is made, and there is no difference. So, no pairs of elements are removed, from the new vector. The next element of the given vector is copied to the new vector. The new vector now has the state (content),
6, 6, 6
Comparison of the first and last elements of the new vector are made, and there is no difference. So, no pairs of elements are removed (the first and the last elements of the new vector are not removed). The next element from the given vector to be copied is 8. The new vector becomes,
6, 6, 6, 8
The first and the last elements of the new vector are different, so they are removed, leaving the new vector with:
6, 6
The next and last element from the given vector to be copied is 8. The new vector becomes,
6, 6, 8
The first and the last elements of the new vector are different, so they are removed, leaving the new vector with:
6
If at this point, the new vector is empty, then no leader exists in the list. This also means that no majority element exists in the list. If the size of the new vector at this point is one or more, then the value it contains is the candidate. There can be more than one occurrence of the candidate, at this stage, in the new vector. Despite that, the next thing to do, is another O(n) operations, to verify if the candidate is the leader, occurring more than n/2 times in the given list (vector). The program for O(n+n) time is as follows:
#include <iostream>The output is 6 as expected. Some new vector methods (member functions) have been introduced here. They are push_back(), front(), back(), erase(), begin() and pop_back(). push_back() appends an element at the back of the vector. front() copies out the value of the first element of the vector without erasing the first element. back() copies out the value of the last element of the vector without erasing the last element. erase() erases an element including its value and index. The argument of the erase method is an iterator that points to the element. newVtr.begin() results in an iterator that points to the first element of the vector, newVtr. pop_back() pops off the last element of the vector, including its value and index.
#include <vector>
using namespace std;
int fastLeader(vector<int> A) {
int n = A.size();
int leader = -1;
vector<int> newVtr = {A[0]};
// O(n) time
for (int i=1; i<n; i++) {
newVtr.push_back(A[i]);
if (newVtr.size() > 1) {
if (newVtr.front() != newVtr.back()) {
newVtr.erase(newVtr.begin());
newVtr.pop_back();
}
}
}
int candidate = -1;
if (newVtr.size() != 0)
candidate = newVtr[0];
else
leader = -1;
int count = 0;
// Another O(n) time
for (int i=0; i<n; i++) {
if (A[i] == candidate)
count += 1;
if (count > n/2) {
leader = candidate;
break;
}
}
return leader;
}
int main(int argc, char **argv)
{
vector<int> A = {6, 8, 4, 6, 8 ,6, 6};
int ret = fastLeader(A);
cout << ret << endl;
return 0;
}