Problem: Write a Java program to find and print the most 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:

```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```

Before we discuss the efficient way to solve this problem, let’s see the approach that involves sorting the array.

## Method 1: Sort and Count the adjacent elements [O(nlogn)]

In this method, we sort the given array (O(nlogn)) to bring the duplicates elements together and count the similar adjacent element to get the most repeated element by iterating through the array.

Sorting the array makes it easier to count the frequency of each element in O(n) time complexity.

To find the number with the highest frequency in the given array using this approach, we need to follow the following steps:

1. Sort the array in ascending order.
2. Loop through the array and count the frequency of each element.
3. Check for each number if their frequency is greater than the old max frequency.
4. If so, then update the max frequency and note the number.
5. Repeat the steps for all distinct elements.
6. Output the number which has the highest frequency or repeated the most number of times in the array.

Initially, the max frequency will be `Integer.MIN_VALUE`, which is the minimum available integer supported by the machine.

Here is the Java program that implements the above steps to find the most repeated element in an array:

``````import java.util.Arrays;

public class Main
{
public static void main(String[] args) {
int element = Integer.MIN_VALUE, max_count=1, count=1;

//intial array
int arr[] = {2, 4, 6, 4, 2, 4, 5, 8};

//sort array in the ascending Order
Arrays.sort(arr);

//loop through the array elements
for(int i=1; i<arr.length; i++){
//count the successive elements as long as they are same
if(arr[i] == arr[i-1])
count++;

if(arr[i] != arr[i-1] || i==arr.length-1){
//compare the count with max_count
if(count>max_count){

//update if count is greater
max_count = count;
element = arr[i-1];
}
//reset count to 1
count =1;
}
}

//output the most repeated element along with the count
System.out.println(element+": "+max_count);
}
}``````

Output: 4:3

Time Complexity: O(nlogn)
Space Complexity: O(1)

Because the array was initially not sorted, the time complexity of the program reached O(nlogn) otherwise we would have solved the problem in O(n).

## Method 2: Using Auxiliary Array to Store the Count [O(n)]

In this method, we use an extra array to store the count of each array element.

We declare an extra array of size equal to the `max_element +1` and assume that its index represents the elements of the original array.

We then loop through the elements of the original array and increment the count as `count_array[array[i]]++`.

Finally, we fetch the count of each element and print the one which has the largest array element.

``````public class Main {
public static void main(String[] args) {
//intial array
int arr[] = {2, 4, 6, 4, 2, 4, 5, 8};
int max_element = 8;

//declare an array of size max_element+1
int count_arr[] = new int[max_element+1];

//loop through the original array and update the count
for(int i=0; i<arr.length; i++){
count_arr[arr[i]]++;
}

//fetch the element having the max count
int max_repeated = Integer.MIN_VALUE;
int max_count = -1;
for(int i=0; i<arr.length; i++){
if(count_arr[arr[i]] > max_count){
max_count = count_arr[arr[i]];
max_repeated = arr[i];
}
}

System.out.println("Most repeated: "+max_repeated);
}
}``````

Output: Most repeated: 4

Time Complexity: O(n)
Space Complexity: O(k), where k is the greatest element in the array.

There are many other ways to find the most repeated element. I have only mentioned what is efficient and best for programming. If you have any doubts or suggestions, comment below.

### This Post Has 7 Comments

1. Mohd Amer Khan

Brilliant explaination thanks a lot

2. Thirumalesh Chinna

Its not O(n), You have to consider the sorting as well

1. Thanks for pointing it out Thirumalesh. I have updated the solution.

3. Abrar

in first method you are not considering if the biggest element is most frequent.for checking that you have to put

if(count>max_count){
max_count = count;
element = arr[i-1];
}

outside?under for loop

1. 4. 1. 