Algorithm Cheat Sheet: Majority Element

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.

Boyer-Moore majority vote algorithm

Boyer-Moore 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 non-zero 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.

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 one-third majority. An array can have at most two one-third majority elements. Similar to the idea of Boyer-Moore majority vote algorithm, here we maintain two counters while recording two potential majority elements. As we scan each element of the array:

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

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

  3. 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 one-third 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 one-third 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 Boyer-Moore majority vote algorithm. When there exists two unique one-third majority elements, at some point both of them will be associated with the two counters respectively, and thus won’t affect each other.

Contents