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

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.