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)

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];
}