*1.7K*

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.