# Maximum repeating element in an array in Java

Problem: Write a Java program to find maximum repeating element in an array of integers in Java. Or write a program to find most popular element in an array.
Maximum repeating element is also called most popular element.
Example:
1.    If the given array is {3, 4, 2, 1, 3, 5, 6, 1, 3}, then the maximum repeating element in the array is 3
2.    If the given array is {2, 5, 3, 5, 3, 2, 4, 5, 2}, then in the array 5 and 2 appears thrice, so the maximum repeating elements are 5 and 2.

## Algorithm to find maximum repeating element in an array

```Say A is an input array with n elements.
1. Create frequency map of the array elements. Say M is frequency map.

2. Initialize count = 2 // Counter to hold frequency of maximum repeating elements

3. Create a list to store maximum repeating elements, maxRepeatingElements

4. Iterate over the frequency map, M
while map has entries
entry = next entry

if entry.value > count
1. Clear elements from maxRepeatingElements
3. count = entry.value

Else If entry.value = count
2. count = entry.value

End If
End while

5. Return maxRepeatingElements```

Analysis:

Above algorithm has 2 steps.
1. Create frequency map. This takes Ο(n) run-time.
2. Iterate over the frequency map and find maximum repeating elements. This takes Ο(n) run-time.
So, the total run-time of the algorithm is Ο(n) + Ο(n) = 2Ο(n). 2 is a constant so the run-time of the algorithm would be Ο(n).

Java code:

We will implement above algorithm in Java.

```package com.javafries.array;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class MaxRepeatingElementProblem {

private static List<Integer> findMaximumRepeatingElements(int[] arr) {
Map<Integer, Integer> frequencyMap = createElementFrequencyMap(arr);

return getMaxRepeatingElements(frequencyMap);
}

private static List<Integer> getMaxRepeatingElements(
Map<Integer, Integer> frequencyMap) {

List<Integer> repeatingElements = new ArrayList<Integer>();
int count = 2;

Iterator<Entry<Integer, Integer>> iterator = frequencyMap.entrySet()
.iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, Integer> entry = iterator.next();

int value = entry.getValue();
int key = entry.getKey();

if (value > count) {
/* If a new element with more frequency is found then clear the
existing elements */
repeatingElements.clear();
count = value;
} else if (value == count) {
count = value;
}
}
return repeatingElements;
}

private static Map<Integer, Integer> createElementFrequencyMap(int[] arr) {

Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();

for (int key : arr) {
if (frequencyMap.containsKey(key)) {
frequencyMap.put(key, frequencyMap.get(key) + 1);
} else {
frequencyMap.put(key, 1);
}
}

return frequencyMap;
}

private static void print(List<Integer> list) {
for (Integer number : list) {
System.out.println(number);
}
}

public static void main(String[] args) {

int[] arr = { 2, 5, 3, 5, 3, 2, 4, 5, 2 };
// int[] arr = { 3, 4, 2, 1, 3, 5, 6, 1, 3 };
List<Integer> maximumRepeatingElements = findMaximumRepeatingElements(arr);

System.out.println("Maximum repeating elements are : ");
print(maximumRepeatingElements);
}
}
```

Output:

```Maximum repeating elements are :
2
5
```

I hope you understood and liked the solution.