least common element

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

Reference

Leave a Reply

avatar
  Subscribe  
Notify of