Given an array arr[] consisting of N integers, the task is to find the maximum element with the minimum frequency.
Examples:
Input: arr[] = {2, 2, 5, 50, 1}
Output: 50
Explanation:
The element with minimum frequency is {1, 5, 50}. The maximum element among these element is 50.Input: arr[] = {3, 2, 5, 6, 1}
Output: 6
Approach: Sort the array in non-decreasing order, which brings elements with the same value together. This allows us to easily count and identify when the frequency of an element changes. When the frequency changes (‘currFreq’ <= ‘minFreq’), we update the minimum frequency and as the array is sorted, the current element (arr[i-1]) becomes the maximum element, representing the highest value within its frequency group.
Follow the steps below to solve the given problem:
- Sort the input array in non-decreasing order.
- Initialize minFreq to array size+1, maxElement to the first element of the sorted array, and currFreq to 1.
- Iterate over the sorted array from the second element to the last element.
- If the current element is the same as the previous element, increment currFreq.
- Otherwise, If currFreq is less than or equal to minFreq, update minFreq with currFreq and update maxElement with the previous element.
- Reset currFreq to 1 for the new element.
- After the loop, check the frequency of the last element and update minFreq and maxElement if necessary.
- Return the maxElement, which represents the maximum element with the minimum frequency in the input array.
C++14
// C++ code for the above approach#include <bits/stdc++.h>using namespace std;int maxElementWithMinFreq(int *arr, int N){ sort(arr, arr + N); // Sort the array in non-decreasing order int minFreq = N + 1; // Initialize minFreq to a value greater than the array size int maxElement = arr[0]; // Initialize maxElement to the first element of the sorted array int currFreq = 1; // Keep track of the frequency of the current element // Iterate over the sorted array for (int i = 1; i < N; i++) { if (arr[i] == arr[i - 1]) { currFreq++; // Increment the frequency if the current element is the same as the previous element } else { // If the frequency of the current element is less than minFreq, update minFreq and maxElement if (currFreq <= minFreq) { minFreq = currFreq; maxElement = arr[i - 1]; } currFreq = 1; // Reset the frequency for the new element } } // Check the frequency of the last element if (currFreq <= minFreq) { minFreq = currFreq; maxElement = arr[N - 1]; } return maxElement; // Return the maximum element with the minimum frequency}int main(){ int arr[] = {2, 2, 5, 50, 1}; int N = sizeof(arr) / sizeof(arr[0]); cout << maxElementWithMinFreq(arr, N); return 0;}//This code is contributed by Abhishek Kumar |
Java
// Java code for the above approachimport java.util.Arrays;public class gfg { public static int maxElementWithMinFreq(int[] arr, int N) { Arrays.sort(arr); // Sort the array in non-decreasing order int minFreq = N + 1; // Initialize minFreq to a value greater than the array size int maxElement = arr[0]; // Initialize maxElement to the first element of the sorted array int currFreq = 1; // Keep track of the frequency of the current element // Iterate over the sorted array for (int i = 1; i < N; i++) { if (arr[i] == arr[i - 1]) { currFreq++; // Increment the frequency if the current element is the same as the previous element } else { // If the frequency of the current element is less than minFreq, update minFreq and maxElement if (currFreq <= minFreq) { minFreq = currFreq; maxElement = arr[i - 1]; } currFreq = 1; // Reset the frequency for the new element } } // Check the frequency of the last element if (currFreq <= minFreq) { minFreq = currFreq; maxElement = arr[N - 1]; } return maxElement; // Return the maximum element with the minimum frequency } public static void main(String[] args) { int[] arr = {2, 2, 5, 50, 1}; int N = arr.length; System.out.println(maxElementWithMinFreq(arr, N)); }} |
Python3
# Python code for the above approachdef max_element_with_min_freq(arr): arr.sort() # Sort the array in non-decreasing order # Initialize min_freq to a value greater than the array size min_freq = len(arr) + 1 # Initialize max_element to the first element of the sorted array max_element = arr[0] curr_freq = 1 # Keep track of the frequency of the current element # Iterate over the sorted array for i in range(1, len(arr)): if arr[i] == arr[i - 1]: curr_freq += 1 # Increment the frequency if the current element is the same as the previous element else: # If the frequency of the current element is less than min_freq, update min_freq and max_element if curr_freq <= min_freq: min_freq = curr_freq max_element = arr[i - 1] curr_freq = 1 # Reset the frequency for the new element # Check the frequency of the last element if curr_freq <= min_freq: min_freq = curr_freq max_element = arr[-1] return max_element # Return the maximum element with the minimum frequencyarr = [2, 2, 5, 50, 1]print(max_element_with_min_freq(arr)) |
C#
using System;class GFG{ static int MaxElementWithMinFreq(int[] arr, int N) { Array.Sort(arr); // Sort the array in non-decreasing order int minFreq = N + 1; // Initialize minFreq to a value greater than the array size int maxElement = arr[0]; // Initialize maxElement to the first element of the sorted array int currFreq = 1; // Keep track of the frequency of the current element // Iterate over the sorted array for (int i = 1; i < N; i++) { if (arr[i] == arr[i - 1]) { currFreq++; // Increment the frequency if the current element is the same as the previous element } else { // If the frequency of the current element is less than minFreq, update minFreq and maxElement if (currFreq <= minFreq) { minFreq = currFreq; maxElement = arr[i - 1]; } currFreq = 1; // Reset the frequency for the new element } } // Check the frequency of the last element if (currFreq <= minFreq) { minFreq = currFreq; maxElement = arr[N - 1]; } return maxElement; // Return the maximum element with the minimum frequency } static void Main() { int[] arr = { 2, 2, 5, 50, 1 }; int N = arr.Length; Console.WriteLine(MaxElementWithMinFreq(arr, N)); }} |
Javascript
function maxElementWithMinFreq(arr) { arr.sort(); // Sort the array in non-decreasing order let minFreq = arr.length + 1; // Initialize minFreq to a value greater than the array size let maxElement = arr[0]; // Initialize maxElement to the first element of the sorted array let currFreq = 1; // Keep track of the frequency of the current element // Iterate over the sorted array for (let i = 1; i < arr.length; i++) { if (arr[i] == arr[i - 1]) { currFreq++; // Increment the frequency if the current element is the same as the previous element } else { // If the frequency of the current element is less than minFreq, update minFreq and maxElement if (currFreq <= minFreq) { minFreq = currFreq; maxElement = arr[i - 1]; } currFreq = 1; // Reset the frequency for the new element } } // Check the frequency of the last element if (currFreq <= minFreq) { minFreq = currFreq; maxElement = arr[arr.length - 1]; } return maxElement; // Return the maximum element with the minimum frequency}const arr = [2, 2, 5, 50, 1];console.log(maxElementWithMinFreq(arr)); |
Output
50
Time Complexity: O(N*log(N))
Auxiliary Space: O(1)
Approach: The given problem can be solved by storing the frequency of the array element in a HashMap and then finding the maximum value having a minimum frequency. Follow the steps below to solve the given problem:
- Store the frequency of each element in a HashMap, say M.
- Initialize two variables, say maxValue as INT_MIN and minFreq as INT_MAX that store the resultant maximum element and stores the minimum frequency among all the frequencies.
- Iterate over the map M and perform the following steps:
- If the frequency of the current element is less than minFreq then update the value of minFreq to the current frequency and the value of maxValue to the current element.
- If the frequency of the current element is equal to the minFreq and the value of maxValue is less than the current value then update the value of maxValue to the current element.
- After completing the above steps, print the value of maxValue as the resultant element.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum element// with the minimum frequencyint maxElementWithMinFreq(int* arr, int N){ // Stores the frequency of array // elements unordered_map<int, int> mp; // Find the frequency and store // in the map for (int i = 0; i < N; i++) { mp[arr[i]]++; } // Initialize minFreq to the maximum // value and minValue to the minimum int minFreq = INT_MAX; int maxValue = INT_MIN; // Traverse the map mp for (auto x : mp) { int num = x.first; int freq = x.second; // If freq < minFreq, then update // minFreq to freq and maxValue // to the current element if (freq < minFreq) { minFreq = freq; maxValue = num; } // If freq is equal to the minFreq // and current element > maxValue // then update maxValue to the // current element else if (freq == minFreq && maxValue < num) { maxValue = num; } } // Return the resultant maximum value return maxValue;}// Driver Codeint main(){ int arr[] = { 2, 2, 5, 50, 1 }; int N = sizeof(arr) / sizeof(arr[0]); cout << maxElementWithMinFreq(arr, N); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find the maximum element// with the minimum frequencystatic int maxElementWithMinFreq(int[] arr, int N){ // Stores the frequency of array // elements HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); // Find the frequency and store // in the map 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); } } // Initialize minFreq to the maximum // value and minValue to the minimum int minFreq = Integer.MAX_VALUE; int maxValue = Integer.MIN_VALUE; // Traverse the map mp for (Map.Entry<Integer,Integer> x : mp.entrySet()){ int num = x.getKey(); int freq = x.getValue(); // If freq < minFreq, then update // minFreq to freq and maxValue // to the current element if (freq < minFreq) { minFreq = freq; maxValue = num; } // If freq is equal to the minFreq // and current element > maxValue // then update maxValue to the // current element else if (freq == minFreq && maxValue < num) { maxValue = num; } } // Return the resultant maximum value return maxValue;}// Driver Codepublic static void main(String[] args){ int arr[] = { 2, 2, 5, 50, 1 }; int N = arr.length; System.out.print(maxElementWithMinFreq(arr, N));}}// This code is contributed by shikhasingrajput |
Python3
# Python 3 program for the above approachimport sysfrom collections import defaultdict# Function to find the maximum element# with the minimum frequencydef maxElementWithMinFreq(arr, N): # Stores the frequency of array # elements mp = defaultdict(int) # Find the frequency and store # in the map for i in range(N): mp[arr[i]] += 1 # Initialize minFreq to the maximum # value and minValue to the minimum minFreq = sys.maxsize maxValue = -sys.maxsize-1 # Traverse the map mp for x in mp: num = x freq = mp[x] # If freq < minFreq, then update # minFreq to freq and maxValue # to the current element if (freq < minFreq): minFreq = freq maxValue = num # If freq is equal to the minFreq # and current element > maxValue # then update maxValue to the # current element elif (freq == minFreq and maxValue < num): maxValue = num # Return the resultant maximum value return maxValue# Driver Codeif __name__ == "__main__": arr = [2, 2, 5, 50, 1] N = len(arr) print(maxElementWithMinFreq(arr, N)) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the maximum element// with the minimum frequencystatic int maxElementWithMinFreq(int []arr, int N){ // Stores the frequency of array // elements Dictionary<int, int> mp = new Dictionary<int,int>(); // Find the frequency and store // in the map for (int i = 0; i < N; i++) { if(mp.ContainsKey(arr[i])) mp[arr[i]]++; else mp.Add(arr[i],1); } // Initialize minFreq to the maximum // value and minValue to the minimum int minFreq = Int32.MaxValue; int maxValue = Int32.MinValue; // Traverse the map mp foreach(KeyValuePair<int,int> x in mp) { int num = x.Key; int freq = x.Value; // If freq < minFreq, then update // minFreq to freq and maxValue // to the current element if (freq < minFreq) { minFreq = freq; maxValue = num; } // If freq is equal to the minFreq // and current element > maxValue // then update maxValue to the // current element else if (freq == minFreq && maxValue < num) { maxValue = num; } } // Return the resultant maximum value return maxValue;}// Driver Codepublic static void Main(){ int []arr = { 2, 2, 5, 50, 1 }; int N = arr.Length; Console.Write(maxElementWithMinFreq(arr, N));}}// This code is contributed by SURENDRA_GANGWAR. |
Javascript
<script> // JavaScript Program to implement // the above approach // Function to find the maximum element // with the minimum frequency function maxElementWithMinFreq(arr, N) { // Stores the frequency of array // elements let mp = new Map(); // Find the frequency and store // in the map for (let i = 0; i < N; i++) { if (mp.has(arr[i])) { mp.set(arr[i], mp.get(arr[i]) + 1); } else { mp.set(arr[i], 1); } } // Initialize minFreq to the maximum // value and minValue to the minimum let minFreq = Number.MAX_VALUE let maxValue = Number.MIN_VALUE; // Traverse the map mp for (let [key, value] of mp) { let num = key; let freq = value; // If freq < minFreq, then update // minFreq to freq and maxValue // to the current element if (freq < minFreq) { minFreq = freq; maxValue = num; } // If freq is equal to the minFreq // and current element > maxValue // then update maxValue to the // current element else if (freq == minFreq && maxValue < num) { maxValue = num; } } // Return the resultant maximum value return maxValue; } // Driver Code let arr = [2, 2, 5, 50, 1]; let N = arr.length; document.write(maxElementWithMinFreq(arr, N));// This code is contributed by Potta Lokesh </script> |
Output
50
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
