Find the element which appears maximum number of times in an array? (Method 2)

Question: Given an array of n numbers. Give an algorithm for finding the element which appears maximum number of times in the array?

Input: 3, 2, 1, 2, 2, 3
Output: 2

This problem can be done by brute force method. Now let us try to optimize this problem further. We need to reduce the time complexity. We used 2 for loops in the brute force approach. This is not necessary. Another approach can be:-

• Sort the entire array.
• Start scanning the array from the beginning and keep counting the elements.
• Compare the count with the current maxCount.
• Return the element with max count.

Here is an implementation of the same:-

int maxDuplicatesSortArray(int arr[], int size)
{
	//returns the sorted array.
	quickSort(arr, size);

	int i;
	int maxCount = 0, maxCount_index = 0;

	int count;
	//do a single scan of the array
	for(i=0;i<size-1;i++)
	{
		count = 0;
		//keep counting till the elements are same
		while(arr[i] == arr[i+1])
		{
			count++;
			i++;
		}

		//update the maxCount and maxCount_index
		if(count > maxCount)
		{
			maxCount = count;
			maxCount_index = i;
		}
	}

	return arr[maxCount_index];
}

You can download the running sample code here.

Time Complexity:- O(nlog(n)) based on the sorting algorithm used.
Space Complexity:- O(1)

Note: This method changes the original array.

Another approach to solve this problem when the range is defined as 0 to n-1.