Java Program to Find Most Repeated Element in O(n)

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

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.

solving max repeated element in array

Let’s do the same in Java.

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);    
}
}

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.

Leave a Reply Cancel reply