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.


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.

solving max repeated element in 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
        //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])
            if(arr[i] != arr[i-1] || i==arr.length-1){
                //compare the count with 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++){
        //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. Adarsh Kumar

      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

    max_count = count;
    element = arr[i-1];

    outside?under for loop

    1. Adarsh Kumar

      Oh, I noticed. Thanks, I have updated the program.

  4. Sumu

    Method 1: Sort and Count the adjacent elements [O(nlogn)] ..logic of this code is wrong. try with int arr[] = {2,0,1,2,2}; this input ,codewill fail to show output

    1. Adarsh Kumar

      Thanks, Sumu for pointing this. It was because the update was only happening on mismatch. I have updated the code and it’s working fine now.

Leave a Reply