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
- 2 Ways to Remove Duplicates from Sorted Array – O(n) time
- Programs to Find Common Elements between Two Unsorted Arrays
- Programs to Remove Duplicate Characters from a String in O(n) Time
- Find the Largest and Smallest Number in Unsorted Array – O(n)
- 2 Ways to Find the Duplicates in Array in O(n) time
- Find Numbers Repeated in Array in O(N) time without using Collections
- Remove the Duplicates from Unsorted Array in O(n) Time
- Find Second Largest Element in an Unsorted Array – O(n)
- Program to reverse a string or word
- Find all possible combinations of numbers to print given sum
- Write a Java Program to print multiplication table for any number