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

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

by nikoo28
0 comment 3 minutes read

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.

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More