In this blog, we would be going through a generally asked problem in technical interviews. Consider a problem on an array of integers where on being given ‘N’ integers we need to find the difference between the values of the frequencies of the highest and the least occurring elements in the array. Seems interesting right!?
So here, we would be taking a look at a brief description and explanation of the same problem along with various approaches that one can take towards solving the problem and we would also be covering the solution implementations and algorithmic complexity analysis on the same.
Problem Statement Description and Explanation
Description: So, here, on being given an array of integers one needs to find the difference between the values of the frequencies of the highest and the least occurring elements in it.
The above problem can be better understood using the example below:
Input: a[] = {8, 9, 5, 6, 5, 2, 2, 8, 8, 3, 6}
Output: 2
Explanation:
Most frequently occurring element (3 or 9), as these occur just once
Least frequently occurring element (8), as it occurs thrice so the difference between their frequency counts is 2 (3 - 1)
Input: arr[] = {6, 9, 6, 9}
Output : 0
For also solving this question one can consider the following set of approaches/ideas which are listed as:
Bruteforce approach: One can traverse and loop through all the elements of the array using nested loops and keep track of the counts of the most and the least occurring elements in it. (O(N^2))
Hashing Based approach: One can maintain a hashmap of the counts of the frequencies of all the elements in the array and return the difference of the max and the min frequency counts that are present in the hashmap. (O(N))
Optimised Bruteforce
The first approach that one might think of and try using would be to write nested loops in order to count the frequencies of the elements present in the array and then identify and return the least and most occurring element from it.
But, the above approach can even be further simplified if the complete array is sorted first and then traversed through it to keep the count of the frequencies of the elements which would now only require one to have a single loop. The mentioned approach can be implemented in the following manner:
C++ Program Implementation
// Program in C++ to calculate and return the difference between the most and the least counts of frequencies of elements in an array
#include <bits/stdc++.h>
using namespace std;
int findFrequencyDiff(int arr[], int n)
{
// first we sort the array
sort(arr, arr + n);
int count = 0, max_count = 0, min_count = n;
for (int i = 0; i < (n - 1); i++) {
// then we keep checking the counts of consecutive elements
if (arr[i] == arr[i + 1]) {
count += 1;
}
else {
max_count = max(max_count, count);
min_count = min(min_count, count);
count = 0;
}
}
return (max_count - min_count);
}
// main
int main()
{
int arr[] = {8, 9, 5, 6, 5, 2, 2, 8, 8, 3, 6};
int n = sizeof(arr) / sizeof(arr[0]);
cout << findFrequencyDiff(arr, n) << "\n";
return 0;
}
You can also try this code with Online C++ Compiler
// Program in Java to calculate and return the difference between the most and the least counts of frequencies of elements in an array
import java.util.*;
class Main {
static int findFrequencyDiff(int arr[], int n)
{
// first we sort the array
Arrays.sort(arr);
int count = 0, max_count = 0, min_count = n;
for (int i = 0; i < (n - 1); i++) {
// then we keep checking the counts of consecutive elements
if (arr[i] == arr[i + 1]) {
count += 1;
}
else {
max_count = Math.max(max_count, count);
min_count = Math.min(min_count, count);
count = 0;
}
}
return (max_count - min_count);
}
// main function
public static void main(String[] args)
{
int arr[] = {8, 9, 5, 6, 5, 2, 2, 8, 8, 3, 6};
int n = arr.length;
System.out.println(findFrequencyDiff(arr, n));
}
}
You can also try this code with Online Java Compiler
# Program in Python to calculate and return the difference between the most and the least counts of frequencies of elements in an array
def findFrequencyDiff(arr, n):
# first we sort the array
arr.sort()
count = 0; max_count = 0; min_count = n
for i in range(0, (n-1)):
# then we keep checking the counts of consecutive elements
if arr[i] == arr[i + 1]:
count += 1
else:
max_count = max(max_count, count)
min_count = min(min_count, count)
count = 0
return max_count - min_count
arr = [ 8, 9, 5, 6, 5, 2, 2, 8, 8, 3, 6 ]
n = len(arr)
print (findFrequencyDiff(arr, n))
You can also try this code with Online Python Compiler
Here we are traversing only once in a loop that will be O(N), and for sorting the elements, it will be (N*log(N)).
Space Complexity: O(1)
Since we are using no extra space for the intermediate steps it makes the space complexity a constant.
Hashtable Based Approach
A more efficient approach can be to build a hashmap/hashtable of the frequencies of all the elements that are present in the array and then return the difference between the two frequency values that are the max. and min. in it.
This approach can be implemented in the following manner:
C++ Program Implementation
// Program in C++ to calculate and return the difference between the most and the least counts of frequencies of elements in an array
#include <bits/stdc++.h>
using namespace std;
int findFrequencyDiff(int arr[], int n)
{
// Using a hashmap for keeping frequencies of all elements in the array
unordered_map<int, int> hm;
for (int i = 0; i < n; i++)
hm[arr[i]]++;
// Finding the counts of max and min frequent elements
int max_count = 0, min_count = n;
for (auto x : hm) {
max_count = max(max_count, x.second);
min_count = min(min_count, x.second);
}
return (max_count - min_count);
}
// main
int main()
{
int arr[] = {8, 9, 5, 6, 5, 2, 2, 8, 8, 3, 6};
int n = sizeof(arr) / sizeof(arr[0]);
cout << findFrequencyDiff(arr, n) << "\n";
return 0;
}
You can also try this code with Online C++ Compiler
// Program in Java to calculate and return the difference between the most and the least counts of frequencies of elements in an array
import java.util.*;
class Main
{
static int findFrequencyDiff(int arr[], int n)
{
// Using a hashmap for keeping frequencies of all elements in the array
Map<Integer,Integer> mp = new HashMap<>();
for (int i = 0 ; i < n; i++)
{
if(mp.containsKey(arr[i]))
{
mp.put(arr[i], mp.get(arr[i])+1);
}
else
{
mp.put(arr[i], 1);
}
}
// Finding the counts of max and min frequent elements
int max_count = 0, min_count = n;
for (Map.Entry<Integer,Integer> x : mp.entrySet())
{
max_count = Math.max(max_count, x.getValue());
min_count = Math.min(min_count, x.getValue());
}
return (max_count - min_count);
}
// main
public static void main(String[] args)
{
int arr[] = { 8, 9, 5, 6, 5, 2, 2, 8, 8, 3, 6 };
int n = arr.length;
System.out.println(findFrequencyDiff(arr, n));
}
}
You can also try this code with Online Java Compiler
# Program in Python to calculate and return the difference between the most and the least counts of frequencies of elements in an array
from collections import defaultdict
def findFrequencyDiff(arr,n):
# Using a hashmap for keeping frequencies of all elements in the array
mp = defaultdict(lambda:0)
for i in range(n):
mp[arr[i]]+=1
# Finding the counts of max and min frequent elements
max_count=0;min_count=n
for key,values in mp.items():
max_count= max(max_count,values)
min_count = min(min_count,values)
return max_count-min_count
arr = [ 8, 9, 5, 6, 5, 2, 2, 8, 8, 3, 6 ]
n = len(arr)
print(findFrequencyDiff(arr,n))
You can also try this code with Online Python Compiler
Here we are traversing only once in a loop that will be O(N) after we created a hashtable of the counts of the frequencies for the elements present in the array.
Space Complexity: O(N)
Here, we are using an additional space to create an unordered_map that will take O(N) space in the worst case.
What is the tradeoff that one needs to consider while using the Optimised Hashtable approach?
Since the hashtable/hashmap-based approach requires extra space to store the counts of the frequencies of various elements that are present in the array, the space complexity here is linear (i.e. O(N)) and not a constant (i.e. O(1)).
How do we store values in a hash table?
In the hash table, we store values in the form of key-value pairs.
Which Among the two - map or an unordered_map, uses hashing to store elements?
unordered_map uses hashing to store the elements.
What is the time complexity of hashing?
The overall time complexity of the hash function is O(1).
Why is hashmap preferred over hashtable in some scenarios?
Usually, they both are preferred equally, but in the case of NULL keys, hashmap can store them, whereas hashtable cannot store NULL keys.
Conclusion
In this blog, We have extensively discussed various approaches to solve the problem of finding the difference between the values of the frequencies of the highest and the least occurring elements in a given array. This problem is often rated and categorised as an Easy to a Medium Level problem.
116+ registered 