Maximum repeating element in an array in Java

Problem: Write a Java program to find maximum repeating element in an array of integers in Java. Or write a program to find most popular element in an array.
Maximum repeating element is also called most popular element.
Example:
1.    If the given array is {3, 4, 2, 1, 3, 5, 6, 1, 3}, then the maximum repeating element in the array is 3
2.    If the given array is {2, 5, 3, 5, 3, 2, 4, 5, 2}, then in the array 5 and 2 appears thrice, so the maximum repeating elements are 5 and 2.

Algorithm to find maximum repeating element in an array

Say A is an input array with n elements.
1. Create frequency map of the array elements. Say M is frequency map.

2. Initialize count = 2 // Counter to hold frequency of maximum repeating elements

3. Create a list to store maximum repeating elements, maxRepeatingElements

4. Iterate over the frequency map, M
   while map has entries
     entry = next entry
     
     if entry.value > count
        1. Clear elements from maxRepeatingElements
        2. Add entry.key into maxRepeatingElements
        3. count = entry.value

     Else If entry.value = count
        1. Add entry.key to maxRepeatingElements
        2. count = entry.value

     End If
   End while

5. Return maxRepeatingElements

 

Analysis:

Above algorithm has 2 steps.
1. Create frequency map. This takes Ο(n) run-time.
2. Iterate over the frequency map and find maximum repeating elements. This takes Ο(n) run-time.
So, the total run-time of the algorithm is Ο(n) + Ο(n) = 2Ο(n). 2 is a constant so the run-time of the algorithm would be Ο(n).

Java code:

We will implement above algorithm in Java.

package com.javafries.array;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

public class MaxRepeatingElementProblem {

	private static List<Integer> findMaximumRepeatingElements(int[] arr) {
		Map<Integer, Integer> frequencyMap = createElementFrequencyMap(arr);

		return getMaxRepeatingElements(frequencyMap);
	}

	private static List<Integer> getMaxRepeatingElements(
			Map<Integer, Integer> frequencyMap) {

		List<Integer> repeatingElements = new ArrayList<Integer>();
		int count = 2;

		Iterator<Entry<Integer, Integer>> iterator = frequencyMap.entrySet()
				.iterator();
		while (iterator.hasNext()) {
			Map.Entry<Integer, Integer> entry = iterator.next();

			int value = entry.getValue();
			int key = entry.getKey();

			if (value > count) {
				/* If a new element with more frequency is found then clear the
				 existing elements */
				repeatingElements.clear();
				repeatingElements.add(key);
				count = value;
			} else if (value == count) {
				repeatingElements.add(key);
				count = value;
			}
		}
		return repeatingElements;
	}

	private static Map<Integer, Integer> createElementFrequencyMap(int[] arr) {

		Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();

		for (int key : arr) {
			if (frequencyMap.containsKey(key)) {
				frequencyMap.put(key, frequencyMap.get(key) + 1);
			} else {
				frequencyMap.put(key, 1);
			}
		}

		return frequencyMap;
	}

	private static void print(List<Integer> list) {
		for (Integer number : list) {
			System.out.println(number);
		}
	}

	public static void main(String[] args) {

		int[] arr = { 2, 5, 3, 5, 3, 2, 4, 5, 2 };
		// int[] arr = { 3, 4, 2, 1, 3, 5, 6, 1, 3 };
		List<Integer> maximumRepeatingElements = findMaximumRepeatingElements(arr);

		System.out.println("Maximum repeating elements are : ");
		print(maximumRepeatingElements);
	}
}

Output:

Maximum repeating elements are : 
2
5

I hope you understood and liked the solution.
Your questions and comments are most welcome.

Leave a Reply