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

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 most naive method to achieve this in our previous post. To improve the time complexity of our problem we can apply sorting technique. If we sort the array, all the like elements will be placed together. When all similar elements are placed together we do not need 2 loops to maintain the count of elements. What we do is:-

• Step 1: Sort the given array
• Step 2: Start from the first element and set the count as 1.
• Step 3: Keep incrementing the count until we see the same element.
• Step 4: Once we see a different element, reset the count to 1 and repeat with step 3.

So the sample code for the above algorithm can be written as:-

void printMajorityElement(int arr[], int size)
{
	quickSort(arr,size);

	int count = 0;
	int i,j=0;
	int majority = 0;
	int found = 0;

	for(i = 0;i<size;i++)
	{
		count = 1;
		j = i+1;
		if(j == size)
			break;
		while(arr[j] == arr[i])
		{
			count++;
			j++;
		}

		i = j - 1;
		if(count > (size/2))
		{
			found = 1;
			majority = arr[i];
			break;
		}
	}

	if(found)
		printf("Majority element = %d",majority);
	else
		printf("Majority element not present");
}

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

Method 1 – Using sorting.

Method 3 – Using a single scan, better time complexity, faster.