# Find the element which appears maximum number of times in the array.

Objec­tive: Given an array of inte­gers, write a algo­rithm to find the ele­ment which appears max­i­mum num­ber of times in the array.

Exam­ple:

```int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7};
Output: Element repeating maximum no of times: 5, maximum count: 3
```

Approach:

Naive approach: Use 2 loops. Check each ele­ment in the array with all other ele­ments in the array and keep track of its count and also main­tain the max counter which track the ele­ment repeats the max­i­mum num­ber of time.

Time Com­plex­ity : O(n^2) Space Com­plex­ity: O(1)

Code:

Sort­ing approach: Sort the array, this will bring all the dupli­cates together if present. Now nav­i­gate the array and keep track of its count and also main­tain the max counter which track the ele­ment repeats the max­i­mum num­ber of time.

Time Com­plex­ity : O(nlogn) Space Com­plex­ity: O(n) by using merge sort.

Code:

Bet­ter Solu­tion : Use Hashmap. Store the count of each ele­ment of array in a hash table and later check in Hash map which ele­ment has the max­i­mum count — Find dupli­cates in an given array

Time Com­plex­ity : O(n) and Space Com­plex­ity: O(n).

Code:

Bet­ter Solu­tion (Con­di­tional) : O(n) time and O(1) extra space.

• This solu­tion works only if array has pos­i­tive inte­gers and all the ele­ments in the array are in range from 0 to n-1 where n is the size of the array.
• Nav­i­gate the array.
• Update the array as for ith index :- arrA[arrA[i]% n] = arrA[arrA[i]% n] + n;
• Now nav­i­gate the updated array and check which index has the max­i­mum value, that index num­ber is the ele­ment which has the max­i­mum occur­rence in the array.
• See the pic­ture below for more explanation.

Sim­i­lar approach used in prob­lem : if array has all con­sec­u­tive numbers.

Code:

Out­put:

```Element repeating maximum no of times: 5, maximum count: 3
```

#### You may also like...

• Lê Khoa

Buggy code, please change arr to {4, 1, 7, 2, 7, 5, 9, 8, 6, 1, 7, 2, 4, 7};; and see the result.

• tuto­ri­al­hori­zon

Thanks Le, cor­rected it

• Lê Khoa

Actu­ally the line: arrA[index] = arrA[index] + size; has prob­lem, please check … it is seri­ous mistake

• tuto­ri­al­hori­zon

Thanks Le, the prob­lem was in print­ing the result. It was “arrA[maxIndex]%size” , changed it to “maxIn­dex”. Please let us know if you find issues in this or any other posts.

• Lê Khoa

Hi tuto­r­ial, it’s fine now. U are right, just the out­put is not cor­rect as expected. Thanks for your pow­er­ful articles !