The reader is advised to read all the lessons (tutorials) in this full course, in the order presented.

Meaning of Majority Element I

In a list of n elements, the element that occurs more than n/2 times is the majority element. This is actually the absolute majority and not just the majority. n/2 is the integer division (see below).

If the count (frequency of occurrences) array is used to look for the majority element, then the absolute majority element would be the index of the count array whose frequency is more than n/2 (integer division). Do not forget that in the count array, each index is a value in the given array. A value in the count array is the number of occurrences of that index as value in the given array.

Since the approach that uses the count array takes O(n+m) time, that approach will not be used here. A O(n) approach will be used (see below).

Integer Division or Flooring the Quotient

Integer Division or Flooring the Quotient, are very similar things. Consider the following statement:

    Dividend / Divisor = Quotient

The dividend and divisor are whole numbers. The quotient consists of the whole number and a remainder. The remainder can be 0. With integer division, only the whole number part of the quotient is taken and the remainder is abandoned. It does not matter if the remainder is more than half the whole number part, or less, or equal to half. For example 8 / 2 = 4 remainder 0. Here the remainder, 0 is abandoned and 4 is taken. As another example, 9 / 2 = 4 remainder 1. Here, the remainder, 1 is abandoned and 4 is taken.

As other examples: 5 / 2 = 2R1 = 2½ = 2; 4 / 2 = 2R0 = 2; 3 / 2 = 1R1 = 1½ = 1; 1 / 2 = 0R1 = 0½ = 0; 0 / 2 = 0R0 = 0.

Illustration for the Algorithm of Boyer and Moore

Consider the following input array:

    A[] = [6, 4, 5, 6, 6, 5 ,6, 6]

By inspection, 6 is the majority element.

For the purpose of analysis, assume that the first element, 6 is the majority element. For this array, the first element happens to be the majority element, but this is not always the case. The first element does not necessarily have to be the majority element. An element assumed like that is called the candidate. Let the value of a counter, called the voteCount, which was initially set to 0, be 1 now, for the first element that is candidate. Continue to iterate over the array.

The next element, is not the same as 6, it is 4; so decrement the voteCount from 1 to 0. Let the new candidate be 4. Increment the voteCount from 0 to 1. The next element, is not the same as 4, it is 5; so decrement the voteCount from 1 to 0. Let the new candidate be 5. Increment the voteCount from 0 to 1.

The next element, is not the same as 5, it is 6; so decrement the voteCount from 1 to 0. Let the new candidate be 6. Increment the voteCount from 0 to 1. The next element, is the same as 6; so increment the voteCount from 1 to 2. The candidate remains at 6. The next element, is not the same as 6, it is 5; so decrement the voteCount from 2 to 1.

The next element, is the same as 6, while the voteCount is greater than 0; so increment the voteCount from 1 to 2. The candidate remains at 6; so increment the voteCount from 2 to 3. The end of the array is reached and there is no more element.

At the end of the array the voteCount is greater than or equal to 1. This is an indication that the final candidate is a majority element (occurring more than n/2 times). Note that the value of the count element is 3 and not 5, that is greater than n/2.

So, another complete iteration over the given array has to be made, to be sure that the final candidate occurs more than n/2 times.

The voteCount at the end of the array will always be at least 1. This means a second complete iteration over the given array has to be made to know how many times, the final candidate occurs in the given array.

Boyer-Moore Majority Vote Algorithm

The algorithm is based on the fact that if an element occurs more than n/2 times, then all the remaining elements together must occur less than n/2 times.

While traversing the given array, a candidate is maintained and a vote count is also maintained:

- If the current element matches the candidate, increment the vote count.
- If it does not match, decrement the vote count.
- When the vote count becomes 0, it means the previous candidate cannot be the majority element, so select the current element as the new candidate, incrementing the vote count to 1.

By the end of the first traversal, the remaining candidate is the potential majority element. A second traversal is required to verify whether the candidate actually appears more than n/2 times.

At the end of the array (first pass) iteration, the vote count will always be at least 1, for each candidate.

Problem

Given an array A[] of size n, find the element that appears more than n/2 times. If no such element exists, return -1.

Examples:
Input: arr[] = [6, 4, 5, 6, 6, 5 ,6, 6]
Output: 6
Explanation: Element 6 appears 5 times. Since ⌊8/2⌋ = 4, and 5 > 4, 6 is the absolute majority element.

Input: arr[] = [1, 1, 2, 1, 3, 5, 1]
Output: 1
Explanation: Element 1 appears 4 times. Since ⌊7/2⌋ = 3, and 4 > 3, 1 is the absolute majority element.

Input: arr[] = [7]
Output: 7
Explanation: Element 7 appears once. Since ⌊1/2⌋ = 0, and 1 > 0, 7 is the absolute majority element.

Input: arr[] = [2, 13]
Output: -1
Explanation: No element appears more than ⌊2/2⌋ = 1 time, so there is no majority element.

Solve the problem in O(n) time, using the Boyer-Moore Majority Vote Algorithm.

The O(n) Program

The program is (read through the code and comments):

#include <stdio.h>

int solution(int A[], int n, int m) {
    int candidate = A[0];
    int voteCount = 0;
    
    //first pass
    for (int i=0; i < n; i++){
        if (candidate == A[i])
            voteCount = voteCount + 1;
        else
            voteCount = voteCount - 1;
            
        if (voteCount == 0) {
            candidate = A[i];
            voteCount = 1;
        }
    }

    //second pass
    int frequency = 0;
    for (int i=0; i < n; i++){    //looking for candidate with freq > n/2
        if (A[i] == candidate)
            frequency++;
    }
    
    if (frequency > n/2)
        return candidate;

    return -1;  //if no element in given array has freq > n/2
}
  
int main(int argc, char **argv) 
{
    int A1[] = {6, 4, 5, 6, 6, 5 ,6, 6};
    int n1 = sizeof(A1) / sizeof(A1[0]);    //length of given array
    int m1 = 0;
    for (int i=0; i < n1; i++)
        if (A1[i] > m1)
            m1 = A1[i];
    int ret1 = solution(A1, n1, m1);
    printf("%i\n", ret1);
    
    int A2[] = {1, 1, 2, 1, 3, 5, 1};
    int n2 = sizeof(A2) / sizeof(A2[0]);    //length of given array
    int m2 = 0;
    for (int i=0; i < n2; i++)
        if (A2[i] > m2)
            m2 = A2[i];
    int ret2 = solution(A2, n2, m2);
    printf("%i\n", ret2);
    
    int A3[] = {7};
    int n3 = sizeof(A3) / sizeof(A3[0]);    //length of given array
    int m3 = 0;
    for (int i=0; i < n3; i++)
        if (A3[i] > m3)
            m3 = A3[i];
    int ret3 = solution(A3, n3, m3);
    printf("%i\n", ret3);
    
    int A4[] = {2, 13};
    int n4 = sizeof(A4) / sizeof(A4[0]);    //length of given array
    int m4 = 0;
    for (int i=0; i < n4; i++)
        if (A4[i] > m4)
            m4 = A4[i];
    int ret4 = solution(A4, n4, m4);
    printf("%i\n", ret4);
    
    return 0; 
}

The output is:

    6
    1
    7
    -1

and correct.

The time complexity for the called function is actually O(2n), with the first n for the first pass and the second n for the second pass. The coefficient (multiplicand of 2) is usually omitted to quote a time complexity of O(n). Other O(1) times are ignored. The space complexity for the called function is O(n) for the given array. The given array is produced outside called function, but it is also used inside the called function. Other O(1) spaces are ignored.

Thanks for reading.