Find the majority element in an array. (Method 3)

Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted.

Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8.
Output: Majority Element = 8

We discussed the basic 2 methods to approach this problem here:-

• Find majority element. (Method 1)
• Find majority element. (Method 2 , using sorting)

It is recommended to have a look at these 2 methods before proceeding with this one. This is the most optimized method and with least space complexity.
Since only one majority element is possible, we can use a simple scan of the input array and keep a track of the count of elements. We basically do not need to keep a count of every element in the array. We first find out the element, that is occurring the maximum times in an array and then we check if its the majority element.
Here is the process:-

• Start from the first element of the array and initialize the count to be = 1, and set it as the majority candidate.
• Start scanning the array.
  • If we get the same element as the majority candidate, then increment the count.
  • If we get a different element, decrease the count by 1.
  • At any moment, if the count is set to 0, that means we have a new majority candidate. Change the majority candidate to the current element and reset the count to 1. This is also known as the Moore’s Voting Algorithm. “Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element. “
  • At the end of the array we will get a majority candidate.
• Now that we have a majority candidate, just scan through the array and see if it appears more than (n/2) times. If yes, this is our majority element.

Here is the implementation of the above algorithm.

#include<stdio.h>

// function to find the majority candidate in a array arr
int findMajorityCandidate(int arr[], int size)
{
	// maj_index - to keep a track of majority candidate
	int maj_index = 0, count = 1;
	int i;

	for(i = 1; i < size; i++)
	{
		// if the element is same as majority candidate
		// increment count
		if(arr[maj_index] == arr[i])
		{
			count++;
		}
		// else, decrease count
		else
		{
			count--;
		}

		// at any time if count becomes 0
		if(count == 0)
		{
			// change the majority cadidate
			maj_index = i;
			count = 1;
		}
	}

	// return the majority candidate
	return arr[maj_index];
}

// a function to print the majority element
void printMajorityElement(int arr[], int size)
{
	// find the majority element
	int candidate = findMajorityCandidate(arr,size);

	int i, count = 0;

	// count the number of occurrences
	for (i = 0; i < size; i++)
	{
		if(arr[i] == candidate)
			count++;
	}
	if (count > size/2)
		printf("Majority element = %d",candidate);
	else
		printf("No majority element found");
}

int main(void)
{
	int arr[] = {8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8};

	printMajorityElement(arr, 17);

	return 0;
}

Time Complexity:- O(n)
Space Complexity:- O(1)