find most common element

Programs to Find Most Common Element in an Unsorted Array

Given an unsorted array as an input, the goal is to find most common element or most frequent element or most repeating element in the array. Let’s solve this problem using the following methods i.e., Method 1: Sorting and Linear Traversal and Method 2: Using Hashing.

Example:

Input: inArray = {2,3,4,5,2,5,6,7,6,8,9,1,5};
Output: Most common element: 5

Algorithm: Method 1- Sorting and Linear Traversal

1) Sort the given array using Arrays.sort().
   The sorting algorithm used in the above method offer O(nlogn) performance.
2) Declare and initialize the following variables:
   current_element_count, max_element_count, most_common_element
3) Traverse through the inArray to find most common element.
   3.1) Check if the current element is equal to previous element
   3.2) else, if current element count is greater than max element count
4) Check if last element is the most common element
5) Print the most common element

Example 1: MostCommonElementArray.java

package com.sneppets.dsalgo.examples;

import java.util.Arrays;

/**
 * program to find most common element/ maximum repeating element in an unsorted array
 * Sorting and Linear Traversal Approach
 * @author sneppets.com
 */
public class MostCommonElementArray {
	
	public static void main (String[] args)
	{
		int[] inArray = {2,3,4,5,2,5,6,7,6,8,9,1,5};
		int arraySize = inArray.length;
	    findMostCommonElement(inArray,arraySize);
	}

	private static void findMostCommonElement(int[] inArray, int arraySize) {
		
		//sort the given array using Arrays.sort().
		//The sorting algorithm used in the above method offer O(nlogn) performance
		Arrays.sort(inArray);
		
		//declare and initialize current_element_count, max_element_count, most_common_element
		int current_element_count = 1;
		int max_element_count = 1;
		int most_common_element = inArray[0];
		
		//Traverse through the array to find most common element
		for(int i=1; i<arraySize; i++)
		{
			//if the current element is equal to previous element
			if(inArray[i] == inArray[i-1])
			{
				current_element_count++;
			}
			else {
				//else, if current element count is greater than max element count
				if(current_element_count > max_element_count)
				{
					max_element_count = current_element_count;
					most_common_element = inArray[i-1];
				}
				current_element_count = 1;
			}
		}
		
		//If last element is the most common element
		if(current_element_count > max_element_count)
		{
			max_element_count = current_element_count;
			most_common_element = inArray[arraySize-1];
		}		
		//print the most common element
		System.out.println("Most common element: " + most_common_element);		
	}
}

Output:

Most common element: 5

Time Complexity – O(nlogn) – Since the algorithm used in Arrays.sort() offer O(nlogn) performance.

Space Complexity – O(1)

Algorithm: Method 2- Use Hashing

Using Hashing to find the most common element is the efficient solution. Below is the algorithm for the same.

1) Create hashmap
2) Traverse through the array and insert all the elements in hashmap
   2.1) if map contains the current element already, get the element count for the current element,
        increment the count, then update element count in the hash map for the given key.
   2.2) else, insert the current element in hashmap and update count as 1
3) Declare and initialize the following variables: most_common_element, max_element_count.
4) Iterate through hashmap's entrySet and find the most common element.
5) Print the most common element.

Example 2: MostCommonElementArrayHashing.java

package com.sneppets.dsalgo.examples;

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

/**
 * program to find most common element/ maximum repeating element in an unsorted array
 * Using Hashing Approach
 * @author sneppets.com
 */

public class MostCommonElementArrayHashing {
	
	public static void main (String[] args)
	{
		int[] inArray = {2,3,4,5,2,5,6,7,6,8,9,1,5};
		int arraySize = inArray.length;
	    findMostCommonElement(inArray,arraySize);
	}

	private static void findMostCommonElement(int[] inArray, int arraySize) {
		
		//Create hashmap
		Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
		
		//Traverse through the array and insert all the elements in HashMap
		for(int i=0; i<arraySize; i++)
		{
			int key = inArray[i];
			//if map contains the current element already
			if(hashMap.containsKey(key))
			{
				//if yes, get the element count for the current element
				int element_count = hashMap.get(key);
				//increment the count
				element_count++;				
				//update element count in the hash map for the given key
				hashMap.put(key, element_count);
			}
			else
			{
				//else, insert the current element in hashmap and update count as 1
				hashMap.put(key, 1);
			}
		}
		//To find the most_common_element using max_element_count 
		//declare and initialize the following variables
		int max_element_count = 0;
		int most_common_element = inArray[0];
		
		//Iterate through hashmap's entrySet and find the most common element
		for(Entry<Integer, Integer> entry : hashMap.entrySet())
		{
			if(max_element_count < entry.getValue())
			{
				most_common_element = entry.getKey();
				max_element_count = entry.getValue();
			}
		}
		//print the most common element
		System.out.println("Most common element is: "+ most_common_element);
		
	}

}

Output:

Most common element is: 5

Time Complexity – O(n)

Space Complexity – O(n)

Recommended Posts

Reference

Leave a Reply

avatar
  Subscribe  
Notify of