Given an array of n positive integers with many repeating elements. The task is to find the maximum difference between the frequency of any two different elements, such that the element with greater frequency is also greater in value than the second integer.
Examples:
Input : arr[] = { 3, 1, 3, 2, 3, 2 }.
Output : 2
Frequency of 3 = 3.
Frequency of 2 = 2.
Frequency of 1 = 1.
Here difference of frequency of element 3 and 1 is = 3 - 1 = 2.
Also 3 > 1.
Method 1 (Use Hashing): The naive approach can be, find the frequency of each element and for each element find the element having lesser value and lesser frequency than the current element.
Below is the implementation of this approach:
C++
// C++ program to find maximum difference// between frequency of any two element// such that element with greater frequency// is also greater in value.#include<bits/stdc++.h>using namespace std;// Return the maximum difference between// frequencies of any two elements such that// element with greater frequency is also// greater in value.int maxdiff(int arr[], int n){ unordered_map<int, int> freq; // Finding the frequency of each element. for (int i = 0; i < n; i++) freq[arr[i]]++; int ans = 0; for (int i=0; i<n; i++) { for (int j=0; j<n; j++) { // finding difference such that element // having greater frequency is also // greater in value. if (freq[arr[i]] > freq[arr[j]] && arr[i] > arr[j] ) ans = max(ans, freq[arr[i]]-freq[arr[j]]); else if (freq[arr[i]] < freq[arr[j]] && arr[i] < arr[j] ) ans = max(ans, freq[arr[j]]-freq[arr[i]]); } } return ans;}// Driven Programint main(){ int arr[] = { 3, 1, 3, 2, 3, 2 }; int n = sizeof(arr)/sizeof(arr[0]); cout << maxdiff(arr, n) << endl; return 0;} |
Java
// Java program to find maximum difference// between frequency of any two element// such that element with greater frequency// is also greater in value.import java.util.*;class GFG {// Return the maximum difference between// frequencies of any two elements such that// element with greater frequency is also// greater in value.static int maxdiff(int arr[], int n){ Map<Integer, Integer> freq = new HashMap<>(); // Finding the frequency of each element. for (int i = 0; i < n; i++) freq.put(arr[i], freq.get(arr[i]) == null ? 1 : freq.get(arr[i]) + 1); int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // finding difference such that element // having greater frequency is also // greater in value. if (freq.get(arr[i]) > freq.get(arr[j]) && arr[i] > arr[j]) ans = Math.max(ans, freq.get(arr[i]) - freq.get(arr[j])); else if (freq.get(arr[i]) < freq.get(arr[j]) && arr[i] < arr[j] ) ans = Math.max(ans, freq.get(arr[j]) - freq.get(arr[i])); } } return ans;}// Driver Codepublic static void main(String[] args){ int arr[] = { 3, 1, 3, 2, 3, 2 }; int n = arr.length; System.out.println(maxdiff(arr, n));}}// This code is contributed by 29AjayKumar |
Python3
# Python program to find maximum difference # between frequency of any two element # such that element with greater frequency # is also greater in value. from collections import defaultdict# Return the maximum difference between # frequencies of any two elements such that # element with greater frequency is also # greater in value. def maxdiff(arr, n): freq = defaultdict(lambda: 0) # Finding the frequency of each element. for i in range(n): freq[arr[i]] += 1 ans = 0 for i in range(n): for j in range(n): # finding difference such that element # having greater frequency is also # greater in value. if freq[arr[i]] > freq[arr[j]] and arr[i] > arr[j]: ans = max(ans, freq[arr[i]] - freq[arr[j]]) elif freq[arr[i]] < freq[arr[j]] and arr[i] < arr[j]: ans = max(ans, freq[arr[j]] - freq[arr[i]]) return ansarr = [3,1,3,2,3,2]n = len(arr)print(maxdiff(arr,n))# This code is contributed by Shrikant13 |
C#
// C# program to find maximum difference // between frequency of any two element // such that element with greater frequency // is also greater in value. using System;using System.Collections.Generic;class GFG{ // Return the maximum difference between // frequencies of any two elements such that // element with greater frequency is also // greater in value. static int maxdiff(int[] arr, int n) { Dictionary<int, int> freq = new Dictionary<int, int>(); // Finding the frequency of each element. for (int i = 0; i < n; i++) { if (freq.ContainsKey(arr[i])) freq[arr[i]]++; else freq.Add(arr[i], 1); } int ans = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { // finding difference such that element // having greater frequency is also // greater in value. if (freq[arr[i]] > freq[arr[j]] && arr[i] > arr[j]) ans = Math.Max(ans, freq[arr[i]] - freq[arr[i]]); else if (freq[arr[i]] < freq[arr[j]] && arr[i] < arr[j]) ans = Math.Max(ans, freq[arr[j]] - freq[arr[i]]); } } return ans; } // Driver Code public static void Main(String[] args) { int[] arr = { 3, 1, 3, 2, 3, 2 }; int n = arr.Length; Console.WriteLine(maxdiff(arr, n)); }}// This code is contributed by// sanjeev2552 |
Javascript
<script>// JavaScript program to find maximum difference// between frequency of any two element// such that element with greater frequency// is also greater in value.// Return the maximum difference between// frequencies of any two elements such that// element with greater frequency is also// greater in value.function maxdiff(arr, n){ let freq = new Map(); // Finding the frequency of each element. for (let i = 0; i < n; i++) freq.set(arr[i], freq.get(arr[i]) == null ? 1 : freq.get(arr[i]) + 1); let ans = 0; for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { // finding difference such that element // having greater frequency is also // greater in value. if (freq.get(arr[i]) > freq.get(arr[j]) && arr[i] > arr[j]) ans = Math.max(ans, freq.get(arr[i]) - freq.get(arr[j])); else if (freq.get(arr[i]) < freq.get(arr[j]) && arr[i] < arr[j] ) ans = Math.max(ans, freq.get(arr[j]) - freq.get(arr[i])); } } return ans;} // Driver code let arr = [ 3, 1, 3, 2, 3, 2 ]; let n = arr.length; document.write(maxdiff(arr, n)); </script> |
Output
2
Time Complexity: O(n2).
Auxiliary Space: O(n)
Method 2 (Use Hashing and Sorting): The idea is to find all the distinct elements and store them in an array, say dist[ ]. Sort the distinct element array dist[] in increasing order. Now for any distinct element at index i, for all index j such that i > j > 0, find the element between index 0 to i-1 having a minimum frequency. We can find the frequency of an element in the same way as method 1, i.e., storing frequencies in a hash table.
So do this for all i and find the maximum difference. To find the minimum frequency for all i maintain a prefix minimum.
Below is the representation of this approach:
C++
// Efficient C++ program to find maximum // difference between frequency of any two // elements such that element with greater // frequency is also greater in value. #include<bits/stdc++.h> using namespace std; // Return the maximum difference between // frequencies of any two elements such that // element with greater frequency is also // greater in value. int maxdiff(int arr[], int n) { unordered_map<int, int> freq; int dist[n]; // Finding the frequency of each element. int j = 0; for (int i = 0; i < n; i++) { if (freq.find(arr[i]) == freq.end()) dist[j++] = arr[i]; freq[arr[i]]++; } // Sorting the distinct element sort(dist, dist + j); int min_freq = n+1; // Iterate through all sorted distinct elements. // For each distinct element, maintaining the // element with minimum frequency than that // element and also finding the maximum // frequency difference int ans = 0; for (int i=0; i<j; i++) { int cur_freq = freq[dist[i]]; ans = max(ans, cur_freq - min_freq); min_freq = min(min_freq, cur_freq); } return ans; } // Driven Program int main() { int arr[] = { 3, 1, 3, 2, 3, 2 }; int n = sizeof(arr)/sizeof(arr[0]); cout << maxdiff(arr, n) << endl; return 0; } |
Java
// Efficient Java program to find maximum // difference between frequency of any two // elements such that element with greater // frequency is also greater in value. import java.util.*;class GFG{ // Return the maximum difference between // frequencies of any two elements such that // element with greater frequency is also // greater in value. static int maxdiff(int arr[], int n) { HashMap<Integer,Integer> freq= new HashMap<>(); int []dist = new int[n]; // Finding the frequency of each element. int j = 0; for (int i = 0; i < n; i++) { dist[j++] = arr[i]; if (!freq.containsKey(arr[i])) freq.put(arr[i], 1); else freq.put(arr[i], freq.get(arr[i]) + 1); } // Sorting the distinct element Arrays.sort(dist); int min_freq = n + 1; // Iterate through all sorted distinct elements. // For each distinct element, maintaining the // element with minimum frequency than that // element and also finding the maximum // frequency difference int ans = 0; for (int i = 0; i < j; i++) { int cur_freq = freq.get(dist[i]); ans = Math.max(ans, cur_freq - min_freq); min_freq = Math.min(min_freq, cur_freq); } return ans; } // Driven Program public static void main(String[] args) { int arr[] = { 3, 1, 3, 2, 3, 2 }; int n = arr.length; System.out.print(maxdiff(arr, n) +"\n"); } } // This code is contributed by Rajput-Ji |
Python3
# Efficient Python3 program to find maximum # difference between frequency of any two # elements such that element with greater # frequency is also greater in value. # Return the maximum difference between # frequencies of any two elements such that # element with greater frequency is also # greater in value. def maxdiff(arr, n): freq = {} dist = [0] * n # Finding the frequency of each element. j = 0 for i in range(n): if (arr[i] not in freq): dist[j] = arr[i] j += 1 freq[arr[i]] = 0 if (arr[i] in freq): freq[arr[i]] += 1 dist = dist[:j] # Sorting the distinct element dist.sort() min_freq = n + 1 # Iterate through all sorted distinct elements. # For each distinct element, maintaining the # element with minimum frequency than that # element and also finding the maximum # frequency difference ans = 0 for i in range(j): cur_freq = freq[dist[i]] ans = max(ans, cur_freq - min_freq) min_freq = min(min_freq, cur_freq) return ans # Driven Program arr = [3, 1, 3, 2, 3, 2]n = len(arr)print(maxdiff(arr, n))# This code is contributed by SHUBHAMSINGH10 |
C#
// Efficient C# program to find maximum// difference between frequency of any two// elements such that element with greater// frequency is also greater in value.using System.Collections.Generic; using System; class GFG{ // Return the maximum difference between// frequencies of any two elements such// that element with greater frequency // is also greater in value.static int maxdiff(int []arr, int n){ Dictionary<int, int> freq = new Dictionary<int, int>(); List<int> dist = new List<int>(); // Finding the frequency of each element. int j = 0; for(int i = 0; i < n; i++) { if (freq.ContainsKey(arr[i]) == false) { dist.Add(arr[i]); j++; } if (freq.ContainsKey(arr[i])) freq[arr[i]]++; else freq[arr[i]]=1; } // Sorting the distinct element dist.Sort(); int min_freq = n + 1; // Iterate through all sorted distinct elements. // For each distinct element, maintaining the // element with minimum frequency than that // element and also finding the maximum // frequency difference int ans = 0; for(int i = 0; i < j; i++) { int cur_freq = freq[dist[i]]; ans = Math.Max(ans, cur_freq - min_freq); min_freq = Math.Min(min_freq, cur_freq); } return ans;}// Driver codepublic static void Main(String[] args) { int []arr = { 3, 1, 3, 2, 3, 2 }; int n = arr.Length; Console.WriteLine(maxdiff(arr, n));}}// This code is contributed by Stream_Cipher |
Javascript
<script>// Efficient Javascript program to find maximum // difference between frequency of any two // elements such that element with greater // frequency is also greater in value. // Return the maximum difference between // frequencies of any two elements such that // element with greater frequency is also // greater in value. function maxdiff(arr, n) { var freq = new Map(); var dist = Array(n); // Finding the frequency of each element. var j = 0; for (var i = 0; i < n; i++) { if (!freq.has(arr[i])) dist[j++] = arr[i]; if(freq.has(arr[i])) freq.set(arr[i], freq.get(arr[i])+1) else freq.set(arr[i], 1) } // Sorting the distinct element dist.sort(); var min_freq = n+1; // Iterate through all sorted distinct elements. // For each distinct element, maintaining the // element with minimum frequency than that // element and also finding the maximum // frequency difference var ans = 0; for (var i=0; i<j; i++) { var cur_freq = freq.get(dist[i]); ans = Math.max(ans, cur_freq - min_freq); min_freq = Math.min(min_freq, cur_freq); } return ans; } // Driven Program var arr = [3, 1, 3, 2, 3, 2 ]; var n = arr.length; document.write( maxdiff(arr, n)) // This code is contributed by famously.</script> |
Output
2
Time Complexity: O(n log n).
Auxiliary Space: O(n)
This article is contributed by Anuj Chauhan(anuj0503). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
