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.

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.

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+m) time.

Note:

Actually, the absolute majority element differs from the majority element. Absolute majority means more than half, and it refers to the element whose frequency of occurrence is more than half of the total number of elements. Majority element simply refers to the element with highest frequency of occurrence and not more than half. In the first example above, 6 is the absolute majority element.

A list may have a majority element but not necessarily the absolute majority element. In the following list, 7 is the majority element and not the absolute majority element.

    [9, 9, 8, 8, 7, 7, 7, 7]

The order of element arrangement of the list does not matter.

The topic is on majority Element I, and it is the absolute majority element that is required, and not just the majority element. In life, absolute majority is still called the majority, but not in this topic. More than n/2 refers to absolute majority.

Note: Solving this problem the brute-force (naive) way will take n² time, and that approach is not recommended.

Strategy

Produce a count array for each of the elements in the given list in O(n) time. Iterate over the count array in O(m) time, looking for the element (index) with frequency that is higher than n/2. The length of the count array is actually m+1, where m is the biggest value in the given array. The +1 for the length, is just in case the list has an element with value 0 (it is the convenience 0 if the given list does not have an element with value 0, because array counting begins from 0, for zero-based indexing).

The O(n+m) Program

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

#include <stdio.h>

int solution(int A[], int n, int m) {
    int count[m+1];
    for (int i=0; i < m+1; i++)
        count[i] = 0;    //initializing count array
    
    for (int i=0; i < n; i++){
        count[A[i]] += 1;   //same as count[A[i]] = count[A[i]] + 1;
    }
    
    for (int i=0; i < m+1; i++){    //looking for index with freq > n/2
        if (count[i] > n/2)
            return i;
    }

    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 O(n+m), with n being the time to iterate over the given array and m being the time to iterate over the count array, looking for the frequency that is greater than n/2 . The time to initialize the count array elements to 0 is ignored. The space complexity for the called function is O(n+m) for the given and count array. The given array is produced outside the called function, but it is also used inside the called function.

Thanks for reading.