Difference between highest and least frequencies in an array

Difficulty Level Easy
Frequently asked in Citadel Fab Fourkites Roblox Tesla
Array Hash SortingViews 3530

The problem “Difference between highest and least frequencies in an array” states that suppose that you have an integer array. The problem statement asks to find out the maximum difference between the highest frequency and lowest frequency of two distinct numbers in an array.

Example

Difference between highest and least frequencies in an array

arr[] = {1, 2, 3, 1, 5, 2, 3, 1 }
2

Explanation

Frequency of 1 → 3 (Highest frequency)

Frequency of 5 → 1 (Lowest frequency)

arr[] = {5, 4, 5, 5, 5, 3, 4 }
3

Explanation

Frequency of 5 → 4 (Highest frequency)

Frequency of 3 → 1 (Lowest frequency)

Algorithm

  1. Declare a Map.
  2. Store and count the frequency of an array element.
  3. Set maxfreq to 0 and minfreq to n.
  4. Traverse the Map:
    1. Find out the maximum value between the maxfreq and frequency in the map and store it to maxfreq.
    2. Find out the minimum value between the minfreq and frequency in the map and store it to minfreq.
  5. Return (maxfreq-minfreq).

Explanation

We have an array of integers. Our task is to find out the maximum difference between the highest occurrence and lowest occurrence of two distinct numbers present in an array. We are going to use hashing. Hashing provides an efficient way to solve this question. We are going to declare a map and count the frequencies of each array element and simultaneously storing the frequencies along with the elements into the map.

Then we will set the value of maxfreq to 0 and minfreq to n, i.e, the length of the array because no element has a frequency greater than the size of the given array. We will traverse the map and picking up every element one by one and checking if it has a frequency greatest or lowest. Separate the maximum frequency to a different variable and minimum frequency to different variable. We need to return the difference between the maximum frequency and lowest frequency, so we will return (maxfreq-minfreq).

Let us take an example:

Example

arr[] = {1, 2, 3, 1, 5, 2, 3, 1 }

When we first traverse the array, we will put the element and their no of occurrences into the map, after traversing we will have the map as:

Map:{ 1:3, 2:2, 3:2, 5:1 }

Now, we have the occurrences of each element in the map, we are going to traverse the map, and picking up each element from the map and check their frequency, which is the greater current frequency or maxfreq and which is the minimum current frequency or minfreq and store it to maxfreq and minfreq respectively.

  • 1:3 →

3 is greater than maxfreq, so maxfreq =3

3 is smaller than minfreq, so minfreq =3

  • 2:2 →

maxfreq is greater than 2, so maxfreq =3

2 is smaller than minfreq, so minfreq =2

  • 3:2 →

maxfreq is greater than 2, so maxfreq =3

Nothing is changed in minfreq, minfreq=2

  • 5:1 →

maxfreq is greater than 1, so maxfreq =3

1 is smaller than minfreq, so minfreq =1

And we will return the difference between maxfreq-minfreq → (3-1) = 2.

Code

C++ code to find Difference between highest and least frequencies in an array

#include<iostream>
#include<unordered_map>

using namespace std;

int getMaximumDiff(int arr[], int n)
{
    unordered_map<int, int> freq;
    for (int i = 0; i < n; i++)
        freq[arr[i]]++;

    int maxfreq = 0, minfreq = n;
    for (auto x : freq)
    {
        maxfreq = max(maxfreq, x.second);
        minfreq = min(minfreq, x.second);
    }
    return (maxfreq - minfreq);
}
int main()
{
    int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << getMaximumDiff(arr, n) << "\n";
    return 0;
}

2

Java code to find Difference between highest and least frequencies in an array

import java.util.HashMap;
import java.util.Map;

class diffBWHighFLeastF
{
    public static int getMaximumDiff(int arr[], int n)
    {
        HashMap<Integer,Integer> freq = new HashMap<>();
        for (int i = 0 ; i < n; i++)
        {
            if(freq.containsKey(arr[i]))
            {
                freq.put(arr[i], freq.get(arr[i])+1);
            }
            else
            {
                freq.put(arr[i], 1);
            }
        }
        int maxfreq = 0, minfreq = n;
        for (Map.Entry<Integer,Integer> x : freq.entrySet())
        {
            maxfreq = Math.max(maxfreq, x.getValue());
            minfreq = Math.min(minfreq, x.getValue());
        }
        return (maxfreq - minfreq);
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 2, 3, 1, 5, 2, 3, 1 };
        int n = arr.length;
        System.out.println(getMaximumDiff(arr, n));
    }
}

2

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Here we have simply traversed over the elements of the array keeping a track of their frequencies. All of this costs only O(N) time.

Space Complexity

O(n) where “n” is the number of elements in the array. At most, we can store n elements if all of them are distinct. The space complexity is linear.

Translate »