Given an array, find the least frequent element in it. If there are multiple elements that appear least number of times, print any one of them.
Examples :
Input : arr[] = {1, 3, 2, 1, 2, 2, 3, 1}
Output : 3
3 appears minimum number of times in given
array.
Input : arr[] = {10, 20, 30}
Output : 10 or 20 or 30
A simple solution is to run two loops. The outer loop picks all elements one by one. The inner loop finds frequency of the picked element and compares with the minimum so far. Time complexity of this solution is O(n2)
A better solution is to do sorting. We first sort the array, then linearly traverse the array.
Java
// Java program to find the least frequent element// in an array.import java.io.*;import java.util.*; class GFG { static int leastFrequent(int arr[], int n) { // Sort the array Arrays.sort(arr); // find the min frequency using // linear traversal int min_count = n+1, res = -1; int curr_count = 1; for (int i = 1; i < n; i++) { if (arr[i] == arr[i - 1]) curr_count++; else { if (curr_count < min_count) { min_count = curr_count; res = arr[i - 1]; } curr_count = 1; } } // If last element is least frequent if (curr_count < min_count) { min_count = curr_count; res = arr[n - 1]; } return res; } // driver program public static void main(String args[]) { int arr[] = {1, 3, 2, 1, 2, 2, 3, 1}; int n = arr.length; System.out.print(leastFrequent(arr, n)); }} /*This code is contributed by Nikita Tiwari.*/ |
3
Time Complexity : O(n Log n)
Auxiliary Space : O(1)
An efficient solution is to use hashing. We create a hash table and store elements and their frequency counts as key value pairs. Finally we traverse the hash table and print the key with minimum value.
Java
//Java program to find the least frequent element//in an arrayimport java.util.HashMap;import java.util.Map;import java.util.Map.Entry; class GFG { static int leastFrequent(int arr[],int n) { // Insert all elements in hash. Map<Integer,Integer> count = new HashMap<Integer,Integer>(); for(int i = 0; i < n; i++) { int key = arr[i]; if(count.containsKey(key)) { int freq = count.get(key); freq++; count.put(key,freq); } else count.put(key,1); } // find min frequency. int min_count = n+1, res = -1; for(Entry<Integer,Integer> val : count.entrySet()) { if (min_count >= val.getValue()) { res = val.getKey(); min_count = val.getValue(); } } return res; } // driver program public static void main (String[] args) { int arr[] = {1, 3, 2, 1, 2, 2, 3, 1}; int n = arr.length; System.out.println(leastFrequent(arr,n)); }} // This code is contributed by Akash Singh. |
3
Time Complexity : O(n)
Auxiliary Space : O(n)
Please refer complete article on Least frequent element in an array for more details!
