How to Find Least Common Element in Unsorted Array
Given an unsorted array as an input, the goal is to find least common element or lest frequent element or least 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,4,3,6,3,6,1};
Output: Least common element: 1
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, min_element_count, least_common_element 3) Traverse through the inArray to find the lest common element. 3.1) Check if the current element is equal to previous element 3.2) else, if current element count is lesser than min element count 4) Check if last element is the least common element 5) Print the least common element
Example 1: LeastCommonElementArray.java
package com.sneppets.dsalgo.examples;
import java.util.Arrays;
/**
* Program to find least common element/ least frequent element in an unsorted array
* Sorting and Linear Traversal Approach
* @author sneppets.com
*/
public class LeastCommonElementArray {
public static void main (String[] args)
{
int[] inArray = {2,3,4,5,2,5,4,3,6,3,6,1};
int arraySize = inArray.length;
leastCommonElement(inArray,arraySize);
}
private static void leastCommonElement(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, min_element_count, least_common_element
int current_element_count = 1;
int min_element_count = arraySize+1;
int least_common_element = inArray[0];
//Traverse through the array to find least common element
for(int i=1; i<arraySize; i++)
{
if(inArray[i] == inArray[i-1])
{
current_element_count++;
}
else {
if(current_element_count < min_element_count)
{
min_element_count = current_element_count;
least_common_element = inArray[i-1];
}
current_element_count = 1;
}
}
//If last element is the least common element
if(current_element_count < min_element_count)
{
min_element_count = current_element_count;
least_common_element = inArray[arraySize-1];
}
//print the least common element
System.out.println("Least common element: " + least_common_element);
}
}
Output:
Least common element: 1
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 least 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: least_common_element, min_element_count.
4) Iterate through hashmap's entrySet and find the least common element.
5) Print the least common element.
Example 2: LeastCommonElementArrayHashing.java
package com.sneppets.dsalgo.examples;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
/**
* Program to find least common element/ least frequent element in an unsorted array
* Using Hashing Approach
* @author sneppets.com
*/
public class LeastCommonElementArrayHashing {
public static void main (String[] args)
{
int[] inArray = {2,3,4,5,2,5,4,3,6,3,6,1};
int arraySize = inArray.length;
findLeastCommonElement(inArray,arraySize);
}
private static void findLeastCommonElement(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);
}
}
//Declare and initialize the following variables
int min_element_count = arraySize+1;
int least_common_element = inArray[0];
//Iterate through hashmap's entrySet and find the least common element
for(Entry<Integer, Integer> entry : hashMap.entrySet())
{
if(min_element_count >= entry.getValue())
{
least_common_element = entry.getKey();
min_element_count = entry.getValue();
}
}
//print the least common element
System.out.println("Least common element is: "+ least_common_element);
}
}
Output:
Least common element is: 1
Time Complexity – O(n)
Space Complexity – O(n)
Recommended Posts
- Programs to Find Most Common Element in an Unsorted Array
- 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