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

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.

0 comment

You may also like

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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