Maximum difference between frequency of two elements such that element having greater frequency is also greater

Suppose, you have an integer array. The problem statement asks to find out the maximum difference between the frequency of any two distinct elements of a given array, but the element with the greater frequency should also be greater in value than the other integer.

Table of Contents

Example

Input:

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

Output:

Explanation:

The frequency of 4 → 3

The frequency of 2 → 2

and the frequency of 3 → 1

4(3) – 3(1) = 2 (Integers are also greater and maximum frequency).

Algorithm

Declare a map and an array say ‘distance’ of length n.
Count and store the frequency of elements into the map and simultaneously store the values of the array into a distance array.
Sort the distance array.
Set minimum to n+1 and output to 0.
Traverse the array, while i<j.
1. Find the maximum between the output and the difference between the value of distance [i] and minimum and store it to output.
2. Find the minimum between the minimum and the value of distance [i] and store it to the minimum.
Return output.

Explanation

We are given an integer and we need to find out the maximum difference between the frequency of two elements so that element having greater frequency should also be greater than another integer with the lowest frequency and also be less than a greater integer. We are going to use Hashing and sorting which will help us to make efficient code. First, we will declare a map and an integer array called distance with the same size as of given array.

While traversing the array to store and count the frequency of array elements we also need to store the value of array[i] according to our algorithm. We will set the value of output to 0 and minimum to n+1. This minimum value helps us to find out the minimum among all the frequencies, and in the output variable, we are going to store our maximum difference. Now, we need to sort the array in which we store the values (distance array).

We will traverse the distance array now and we need to traverse up to the value j because in the previous traversal when we are storing the values in distance we were increasing the value of j, so the value of j is the maximum value for the distance array to traverse up. We need to find the maximum distance between the output and the difference between the frequency and minimum value. And store it to output and also we also need to find the minimum value between the minimum and frequency of distance array element and store it to the minimum. This will be continued until we traverse all the values in a distance array. At last, we have the most suitable answer in the output and we will return that output value.

Implementation

C++ program for Maximum difference between frequency of two elements

#include<unordered_map>
#include<iostream>
#include<algorithm>
using namespace std;

int getMaximumDifference(int arr[], int n)
{
    unordered_map<int, int> freq;

    int distance[n];
    int j = 0;
    for (int i = 0; i < n; i++)
    {
        if (freq.find(arr[i]) == freq.end())
            distance[j++] = arr[i];

        freq[arr[i]]++;
    }
    sort(distance, distance + j);

    int minimum = n+1;

    int output = 0;
    for (int i=0; i<j; i++)
    {
        int currentFrequency = freq[distance[i]];
        output = max(output, currentFrequency - minimum);
        minimum = min(minimum, currentFrequency);
    }

    return output;
}
int main()
{
    int arr[] = {2,4,4,4,3,2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMaximumDifference(arr, n) << endl;
    return 0;
}

Java program for Maximum difference between frequency of two elements

import java.util.HashMap;
import java.util.Arrays;
class maximumDifferenceFrequency
{
    public static int getMaximumDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> frequency=new HashMap<>();

        int distance[]=new int[n];
        int j = 0;
        for (int i = 0; i < n; i++)
        {
            if (frequency.containsKey(arr[i]))
            {
                frequency.put(arr[i],frequency.get(arr[i])+1);

            }
            else
            {
                frequency.put(arr[i],1);
            }
            distance[j++] = arr[i];
        }
        Arrays.sort(distance);

        int minimum = n+1;

        int output = 0;
        for (int i=0; i<j; i++)
        {
            int currentFrequency = frequency.get(distance[i]);
            output = Math.max(output, currentFrequency - minimum);
            minimum = Math.min(minimum, currentFrequency);
        }

        return output;
    }
    public static void main(String [] args)
    {
        int arr[] = {2,4,4,4,3,2};
        int n = arr.length;

        System.out.println(getMaximumDifference(arr, n));
    }
}