Find the majority element in an array

Difficulty Level: Medium

Asked in: Microsoft, Google, Amazon, Yahoo

Understanding the Problem

Problem Description: You are given an array A[] consisting of n elements. You need to find and return the number which appears more than n/2 times.

Note: Do not confuse the majority element as just the element with maximum frequency. A majority element occurs more than n/2 times.

For example :

Input: A[] = {3,9,1,3,5,3,3}

Output: 3

Input: A[] = {8,8,8,8,8,10,10}

Output: 8

Possible questions to ask the interviewer:-

Is an element a majority element if it appears exactly n/2 times? ( Ans: No, the majority element needs to appear more than n/2 times)
What should I return if there is no majority element? ( Ans: In that case, return -1, assume that “-1” will never be an element in the input array)

Solutions

We will be discussing five possible solutions for this problem:-

Brute Force Approach: Using two nested loops
Using Sorting
Using Hash Table
Bit Manipulation algorithm
Boyer-Moore Majority Vote Algorithm

1. Brute Force Approach : Using two nested loops

A simple brute force approach for this problem would be to use nested loops and count the frequency of each element. If we reach an element with a frequency greater than n/2, that’s our majority element.

Pseudo-Code

int findMajorityElement(int A[], int n)
{
    for ( i = 0 to n-2 )
    {
        int count = 1
        for ( j = i+1 to n-1 )
        {
            if ( A[i] == A[j] )
                count = count + 1
        }
       if ( count > n/2 )
            return A[i]
    }
    return -1
}

Complexity Analysis

Time Complexity: O(n²) ( Why? )

Space Complexity: O(1)

Critical ideas to think!

How can we improve the time complexity of finding the frequency of an element?
What is the best-case input and what will be the time complexity in that case?

2. Using Sorting

If we sort the array, all similar elements will line up next to each other, it is now easy to check the frequency of each element and can be done in linear time.

Pseudo-Code

int findMajorityElement(int A[], int n)
{
    sort(A, n)
    int i = 1, count = 1
    while ( i < n )
    {
        while ( i < n and A[i] == A[i-1] )
        {
            i = i + 1
            count = count + 1
        }
       if ( count > n/2 )
            return A[i-1]
        count = 1
        i = i + 1
    }
    return -1
}

Complexity Analysis

Time Complexity: Sorting the array + Linear Traversal (Each element is visited only once) = O(nlogn) + O(n) = O(nlogn)

Space Complexity: If we use merge sort, then O(n), else if we use Heap Sort, its O(1)

Critical ideas to think!

How should we use extra space to improve our time complexity of finding the frequency of all elements?

3. Using Hash Table

If we create an auxiliary Hash Table which will store the frequency of each element in linear time and space complexity. We could then traverse the Hash Table and see if any element has a frequency greater than n/2.

Pseudo-Code

int findMajorityElement(int A[], int n)
{
    Create a HashTable H
   for ( i = 0 to n-1 )
    {
        if ( A[i] in H )
            H[A[i]] = H[A[i]] + 1
        else
            H[A[i]] = 1
        
        if ( H[A[i]] > n/2 )
            return A[i]
    }
    return -1
}

Complexity Analysis

Time Complexity: O(n) ( Why? )

Space Complexity: O(n), for storing the auxiliary Hash Table

Critical ideas to think!

Can this problem be solved via a Binary Search Tree using similar logic? What will be the time and space complexity then?

4. Bit Manipulation Algorithms

In this approach, we will deal with the binary representation of the numbers. The algorithm first determines the frequency of each bit in the input array. If there is a number with a majority in the input (i.e. it makes up more than half of the input), then the frequency of all its set bits will be in the majority, and the frequency of all its unset bits will be in the minority.

Solution Steps

We shall be assuming that the elements in the array are within the confines of a 32-bit integer.

Create a loop to iterate from 0 to 32 representing the current bit position.
For each bit position, initialize a variable count = 0
Now iterate the entire array and increase count by 1 if the current bit position is set in an element. ( How to check if the bit at certain position is 1 or 0?)
If the resultant count is greater than n/2, set this bit position in the majority element. ( How do you set a bit at a particular position?)
Check the count of the majority element formed by a linear traversal of the array and return it if the count is greater than n/2, else return -1.

Pseudo-Code

int findMajorityElement(int A[], int n)
{
    int majority_element = 0, count = 0
    for ( curr = 0 to 32 )
    {
        count = 0
        for ( i = 0 to n-1 )
        {
        // Checks if the bit no. 'curr' is set or not in A[i]
            if ( A[i] & (1<<curr) )
                count = count + 1
        }
       if ( count > n/2 )
        {
        // Setting the bit no. 'curr' as 1 in the majority element
            majority_element += (1 << curr)
        }
    }
    count = 0
    for( i = 0 to n-1 )
        if ( A[i] == majority_element )
            count += 1
    
    if ( count > n/2 )
        return majority_element
    else
        return -1
}

Complexity Analysis

Time Complexity: Checking each bit position for entire array + Finding frequency of majority_element = O(32*n) + O(n) = O(n)

Space Complexity: O(1)

Critical ideas to think!

What element will be formed if a majority element does not exist?
What other problems can you solve using similar bit manipulation logic?

5. Boyer-Moore Majority Vote Algorithm

The Boyer-Moore Majority Vote Algorithm finds the majority element if it's guaranteed that the majority element exists. We will just check the frequency of the element found by this algorithm in the end to confirm.

The intuition in the algorithm is that since the majority element occurs more than n/2 times, its frequency is greater than all other elements combined. Therefore, for each occurrence of the majority element, we can cross out one non-majority element.

Solution Steps

Initialize a max_index = 0 and count = 0. The element at index max_index is considered to be our current candidate for majority element.
Traverse the array updating max_index and count according to the following conditions:-

If A[max_index] == A[i], increase count by 1.
Else, decrease count by 1.
If count == 0, max_index = i and count = 1.

3. Check the frequency of the element at max_index via a linear traversal of the array

Pseudo-Code

int findMajorityElement(int A[], int n)
{
    int max_index = 0, count = 0
    for( i = 0 to n-1 )
    {
        if ( A[i] == A[max_index] )
            count += 1
        else
            count -= 1
        
        if ( count == 0 )
        {
            max_index = i
            count = 1
        }
    }
    count = 0
    for ( i = 0 to n-1 )
        if ( A[i] == A[max_index] )
            count += 1
    
    if ( count > n/2 )
        return A[max_index]
    else
        return -1
}