A majority element over a collection is the one that occurs more than half of all the elements in the collection. When there exists a majority, a sorted array has that majority element placed in the middle position. For an unsorted array, a majority element can be identified by the times of its appearance (a hash table can be used to track the appearance of each unique element). Both sorting and hash tables involve certain overhead of time and space. Here we are studying Boyerâ€“Moore majority vote algorithm which identifies the majority element in linear time with constant space.
BoyerMoore majority vote algorithm
BoyerMoore majority vote algorithm maintains a counter with an initial value of zero. It then scans every element of an array. For each element visited, if the counter is zero, it remembers that element as the potential majority element and sets the counter to one. With a nonzero counter value (either positive or negative), if the current element equals to the potential majority element, it increments the counter; otherwise, it decrements the counter. As long as there exists a majority element, in the end the stored potential majority element will be the majority.
// a[1] to a[n] is the array where we are identifying the majority element.
// Suppose the majority element always exists.
int count = 0;
int majority = NULL;
for (int i = 0; i < n; ++i)
{
if (count == 0)
majority = a[i];
if (a[i] == majority)
count++;
else
count;
}
return majority;
The rationale is that a majority element must occur more than any other elements. Because of that, there must be the case (which may occur multiple times) when the counter is zero while we are visiting the majority element (so the counter will be associate with the majority element). There must also be the case when the counter is associate with the majority element while no one else can decrement the counter to zero. Therefore, in the end the majority element can be identified from the counter.
Onethird majority
A majority element is defined to be the one that occurs more than half of the total element number. How about the case that an element appears more than one third of the total element number? Let’s call that a onethird majority. An array can have at most two onethird majority elements. Similar to the idea of BoyerMoore majority vote algorithm, here we maintain two counters while recording two potential majority elements. As we scan each element of the array:

If one of the counters is associated with the current element, we just increment that counter.

Otherwise, if one of the counters is zero, we then associate that counter with the current element and also set its value to one.

When none of the above conditions applies, we have both counters neither zero nor associated with the current element. We then decrement both of them.
// a[1] to a[n] is the array where we are identifying the majority element.
// Suppose the onethird majority element(s) always exist (at most two).
int count1 = 0;
int count2 = 0;
int majority1 = NULL;
int majority2 = NULL;
for (int i = 0; i < n; ++i)
{
if (count1 > 0 && a[i] == majority1)
count1++;
else if (count2 > 0 && a[i] == majority2)
count2++;
// We check the above two conditions first. Otherwhise we may
// have both counters associated with one single element.
else if (count1 == 0)
{
majority1 = a[i];
count1++;
}
else if (count2 == 0)
{
majority2 = a[i];
count2++;
}
else
{
count1;
count2;
}
}
// Because there can be just one single onethird majority element,
// we need to further verify each of them.
count1 = 0;
count2 = 0;
for (int i = 0; i < n; ++i)
{
if (a[i] == majority1)
count1++;
else if (a[i] == majority2)
count2++;
}
if (count1 > n / 3)
result.push_back(majority1);
if (count2 > n / 3)
result.push_back(majority2);
return result;
The rationale is similar to that of BoyerMoore majority vote algorithm. When there exists two unique onethird majority elements, at some point both of them will be associated with the two counters respectively, and thus won’t affect each other.