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

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

To find the number with the highest frequency in a given array, 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.

By sorting the array in ascending order, the duplicates elements come together, as a result, it become easier to count the frequency of each element in O(n).

Overall we are trying to do the following depicted in the following image:

Here is the Java program that implements the above logic 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++;
            else{
                //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(n)
Space Complexity: O(1)

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.