Write a java program to find and print the m**ost repeated element in the array in O(n)**. If there is more than one number having the same highest frequency, then print the smaller value.

**Example:**

1 2 3 4 5 | Input - [1, 7, 2, 6, 6, 8, 1, 3, 2, 6] Output - 6 Input - [1, 3, 2, 5, 9, 2, 1, 3, 1, 2] Output - 1 |

To find the number which has the highest frequency, we have to follow the following steps.

- Sort the array in
**Ascending Order**. - Loop through the array and
**count the frequency of each element**. - Check for each number if thier frequency is greater than the old max frequency.
- If yes then
**update the max frequency**and**note the number**. - Repeat the steps for all distinct elements.
- Output the the number which has highest frequency or repeated most times in the array.

Initially, the max frequency will be `Integer.MIN_VALUE`

, which stores the minimum available integer supported by the machine.

We have sorted the array because the same elements will come together; hence, it will be easier to count the frequency of each element in **O(n)**.

So, overall we are trying to do the following as depicted in the image.

Let’s do the same in Java.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | import java.util.Arrays; public class Main { public static void main(String[] args) { int arr[] = {2, 4, 6, 4, 2, 4, 5, 8}; //Sorting array in Ascending Order Arrays.sort(arr); int element = Integer.MIN_VALUE, max_count=1, count=1; for(int i=1; i<arr.length; i++){ //count the same element if(arr[i] == arr[i-1]) count++; else{ //Compare the counted frequency with max_count if(count>max_count){ //Update if found greater frequency max_count = count; element = arr[i-1]; } //Reset Count count =1; } } System.out.println(element+": "+max_count); } } |

**Output-** 4:3

Time Complexity – **O(n)**

Space Complexity – **O(1)**

There are other several ways to find the most repeated element or the element with the highest frequency. I have only mentioned which is efficient and best for programming.

If you have any doubts or suggestions, then comment below.

## Mohd Amer Khan

9 Dec 2019Brilliant explaination thanks a lot