**Objective: **Given an array of integers, write a algorithm to find the element which appears maximum number of times in the array.

**Example:**

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 element in the array with all other elements in the array and keep track of its count and also maintain the max counter which track the element repeats the maximum number of time.

Time Complexity : O(n^2) Space Complexity: O(1)

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class MaxRepeatingBruteForce { | |

public void MaxRepeatingElement(int [] arrA){ | |

int maxCounter = 0; | |

int element=0; | |

for (int i = 0; i <arrA.length ; i++) { | |

int counter =1; | |

for (int j = i+1; j <arrA.length ; j++) { | |

if(arrA[i]==arrA[j]){ | |

counter++; | |

} | |

} | |

if(maxCounter<counter){ | |

maxCounter=counter; | |

element = arrA[i]; | |

} | |

} | |

System.out.println("Element repeating maximum no of times: " + element + ", maximum count: " + maxCounter); | |

} | |

public static void main(String[] args) { | |

int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7}; | |

MaxRepeatingBruteForce m = new MaxRepeatingBruteForce(); | |

m.MaxRepeatingElement(arrA); | |

} | |

} |

**Sorting approach:** Sort the array, this will bring all the duplicates together if present. Now navigate the array and keep track of its count and also maintain the max counter which track the element repeats the maximum number of time.

Time Complexity : O(nlogn) Space Complexity: O(n) by using merge sort.

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

import java.util.Arrays; | |

public class MaxRepeatingUsingSorting { | |

public void maxRepeatingElementUsingSorting(int [] arrA){ | |

if(arrA.length<1){ | |

System.out.println("Inavlid Array"); | |

return; | |

} | |

Arrays.sort(arrA); | |

int count=1; | |

int maxCount=1; | |

int currentElement = arrA[0]; | |

int maxCountElement =arrA[0]; | |

for (int i = 1; i <arrA.length ; i++) { | |

if(currentElement==arrA[i]){ | |

count++; | |

}else{ | |

if(count>maxCount){ | |

maxCount = count; | |

maxCountElement = currentElement; | |

} | |

currentElement = arrA[i]; | |

count = 1; | |

} | |

} | |

System.out.println("Element repeating maximum no of times: " + maxCountElement + ", maximum count: " + maxCount); | |

} | |

public static void main(String[] args) { | |

int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7}; | |

MaxRepeatingUsingSorting m = new MaxRepeatingUsingSorting(); | |

m.maxRepeatingElementUsingSorting(arrA); | |

} | |

} |

**Better Solution :** Use Hashmap. Store the count of each element of array in a hash table and later check in Hash map which element has the maximum count – Find duplicates in an given array

Time Complexity : O(n) and Space Complexity: O(n).

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

import java.util.HashMap; | |

import java.util.Iterator; | |

import java.util.Map; | |

public class MaxRepeatingUsingHashMap { | |

public void maxRepeatingElementUsingMap(int [] arrA){ | |

//Will store each character and it's count | |

HashMap<Integer, Integer> map = new HashMap<>(); | |

for (int i = 0; i <arrA.length; i++) { | |

if(map.containsKey(arrA[i])){ | |

map.put(arrA[i],map.get(arrA[i])+1); | |

}else{ | |

map.put(arrA[i], 1); | |

} | |

} | |

//traverse the map and track the element which has max count | |

Iterator entries = map.entrySet().iterator(); | |

int maxCount = 0; | |

int element =arrA[0]; | |

while(entries.hasNext()){ | |

Map.Entry entry = (Map.Entry) entries.next(); | |

int count = (Integer)entry.getValue(); | |

if(maxCount<count){ | |

maxCount = count; | |

element = (Integer)entry.getKey(); | |

} | |

} | |

System.out.println("Element repeating maximum no of times: " + element + ", maximum count: " + maxCount); | |

} | |

public static void main(String[] args) { | |

int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7}; | |

MaxRepeatingUsingHashMap m = new MaxRepeatingUsingHashMap(); | |

m.maxRepeatingElementUsingMap(arrA); | |

} | |

} |

**Better Solution** (Conditional) : **O(n) time and O(1) extra space.**

- This solution works only if array has positive integers and all the elements in the array are in range from 0 to n-1 where n is the size of the array.
- Navigate the array.
- Update the array as for ith index :- arrA[arrA[i]% n] = arrA[arrA[i]% n] + n;
- Now navigate the updated array and check which index has the maximum value, that index number is the element which has the maximum occurrence in the array.
- See the picture below for more explanation.

Similar approach used in problem : if array has all consecutive numbers.

**Code:**

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

Learn more about bidirectional Unicode characters

public class MaxRepeatingElement { | |

public void MaxRepeatingElementInPlace(int [] arrA){ | |

int size = arrA.length; | |

int maxCount=0; | |

int maxIndex=0; | |

for (int i = 0; i <size ; i++) { | |

//get the index to be updated | |

int index = arrA[i]% size; | |

arrA[index] = arrA[index] + size; | |

} | |

for (int i = 0; i <size ; i++) { | |

if(arrA[i]/size>maxCount){ | |

maxCount=arrA[i]/size; | |

maxIndex=i; | |

} | |

} | |

System.out.println("Element repeating maximum no of times: " + maxIndex + ", maximum count: " + maxCount); | |

} | |

public static void main(String[] args) { | |

int [] arrA = {4, 1, 5, 2, 1, 5, 9, 8, 6, 5, 3, 2, 4, 7}; | |

MaxRepeatingElement m = new MaxRepeatingElement(); | |

m.MaxRepeatingElementInPlace(arrA); | |

} | |

} |

**Output:**

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

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

Thanks Le, corrected it

Actually the line: arrA[index] = arrA[index] + size; has problem, please check … it is serious mistake

Thanks Le, the problem was in printing the result. It was “arrA[maxIndex]%size” , changed it to “maxIndex”. Please let us know if you find issues in this or any other posts.

Hi tutorial, it’s fine now. U are right, just the output is not correct as expected. Thanks for your powerful articles !