Leader for app.codility.com/programmers Explained in JavaScript
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 JavaScript 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:
<script type='text/javascript'>
function slowLeader(A) {
let n = A.length;
let leader = -1;
for (let i=0; i<n; i++) {
let candidate = A[i];
let count = 0;
for (let j=0; j<n; j++) {
if (A[j] == candidate)
count += 1;
if (count > parseInt(n/2)) {
leader = candidate;
break;
}
}
if (count > parseInt(n/2))
break;
}
return leader;
}
const A = [6, 8, 4, 6, 8 ,6, 6];
let ret = slowLeader(A);
document.write(ret + '<br>');
</script>
The output is 6.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:
<script type='text/javascript'>
function fastLeader(A) {
let n = A.length;
let leader = -1;
A.sort((a, b) => a - b);
let candidate = A[parseInt(n/2)];
let count = 0;
for (let j=0; j<n; j++) {
if (A[j] == candidate)
count += 1;
if (count > parseInt(n/2)) {
leader = candidate;
break;
}
}
return leader;
}
const A = [6, 8, 4, 6, 8 ,6, 6];
let ret = fastLeader(A);
document.write(ret + '<br>');
</script>
The output is 6. The JavaScript 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.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 6 and 8 (next to one another) that are different are removed, the list becomes:
6, 6, 8
Removing the 6 and 8 (next to one another) that are different, leads to a remaining list of:
6
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 empty array object is created. This new array is the stack. The elements of the given array are sent (unshifted) to the new array, one-by-one.
As from the second element, to be 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 is 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 array. That element is the candidate. The candidate may be one or more of the same copies of the same value (in the new array). If the size of the new array ends as zero, then there is no leader. The states of the new array 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 array is:
4
When 6 is copied and added (at the back), the new array becomes:
4, 6
The first and the last elements of the new array are compared. They are not equal, and so the first and last elements of the new array are removed (from the new array). At this point, the new array becomes empty. Next, 6 is copied for the new array to have only 6. No comparison can be made at this stage, since the new array now has only one element. So the fourth element at index 3 of the given array, which is still 6, is copied, to the new array. The state (content) of the new array is now,
6, 6
Comparison of the first and last elements of the new array is made, and there is no difference. So, no pairs of elements are removed, from the new array. The next element of the given array is copied to the new array. The new array now has the state (content),
6, 6, 6
Comparison of the first and last elements of the new array are made, and there is no difference. So, no pairs of elements are removed (the first and the last elements of the new array are not removed). The next element from the given array to be copied is 8. The new array becomes,
6, 6, 6, 8
The first and the last elements of the new array are different, so they are removed, leaving the new array with:
6, 6
The next and last element from the given array to be copied is 8. The new array becomes,
6, 6, 8
The first and the last elements of the new array are different, so they are removed, leaving the new array with:
6
If at this point, the new array 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 array 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 array. 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 (array). The program for O(n+n) time is as follows:
<script type='text/javascript'>
function solution(A) {
let n = A.length;
let leader = -1;
const newArr = [];
// O(n) time
for (let i=0; i<n; i++) {
if (newArr.length == 0)
newArr.unshift(A[i]);
else if (newArr[0] != A[i])
newArr.shift();
else
newArr.unshift(A[i]);
}
let candidate = -1;
if (newArr.length != 0)
candidate = newArr[0];
else
leader = -1;
let count = 0;
// Another O(n) time
for (let i=0; i<n; i++) {
if (A[i] == candidate)
count += 1;
if (count > parseInt(n/2)) {
leader = candidate;
break;
}
}
return leader;
}
const A = [6, 8, 4, 6, 8 ,6, 6];
let ret = solution(A);
document.write(ret + '<br>');
</script>
With this approach (method), the list does not have to be sorted first.