Given an array of integers, return the value that occurs the maximum number of times.
If multiple values occur for the same number of times, return the smallest among them.
If the array is empty return -1.
Example 1
Input: arr = [4, 1, 4, 2, 1]
Output: 1
Explanation: Both 1 and 4 occur twice, which is the highest frequency. But 1 is smaller than 4, so the answer will be 1.
Example 2
Input: arr = []
Output: -1
Explanation: The array is empty, so the ans is -1.
Brute Force Approach
Since we need the element that appears the maximum number of times, the most direct idea is to determine the frequency of every element and compare them.
Algorithm
If the array is empty, return -1.
Pick one element at a time and count how many times it appears in the entire array.
Compare this count with the highest frequency found so far. If the count is higher, update the answer.
If the frequencies are same, choose the smaller element as the answer.
Dry Run
Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the most frequent element in the array. int mostFrequentElement(const vector<int>& arr) { // If the array is empty, there is no answer. if (arr.empty()) { return -1; } int answer = arr[0]; int maxFrequency = 0; // Check every element in the array. for (int i = 0; i < arr.size(); i++) { int currentFrequency = 0; // Count the frequency of the current element. for (int j = 0; j < arr.size(); j++) { // If both elements are equal, increment the frequency. if (arr[j] == arr[i]) { currentFrequency++; } } /* Update the answer if the current element is a better candidate. */ if (currentFrequency > maxFrequency || (currentFrequency == maxFrequency && arr[i] < answer)) { maxFrequency = currentFrequency; answer = arr[i]; } } return answer; }};// Driver Code startsint main() { vector<int> arr = {4, 1, 4, 2, 1}; Solution solution; // Call the function to find the most frequent element. int answer = solution.mostFrequentElement(arr); cout << answer << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N2), where N is the size of the array. For each element, the entire array is traversed once, resulting in N × N operations.
Space Complexity: O(1), because only the current count and best answer are stored apart from the input.
Better Approach
The brute force solution counts the frequency of the same value many times, the makes the solution slow.
A better approach is to sort the array first. Once sorted, all equal values become adjacent, forming continuous groups. Instead of counting the frequency of every element separately, the size of each group is calculated. The largest group represents the most frequent element. If two groups have equal size, the smaller value is the answer.
Algorithm
If the array is empty, return -1.
Sort the array so that all equal values become consecutive and start from the first position of the array.
Mark the beginning of the current group and keep moving forward while the same value continues.
As soon as a different value is found (or the array ends), the current group is complete.
Compute the size of the current group.
If the current group is larger than the best group seen so far, update the answer. If both groups have the same size, keep the smaller value.
Dry Run
better
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the most frequent element in the array. int mostFrequentElement(vector<int>& arr) { // If the array is empty, there is no answer. if (arr.empty()) { return -1; } // Sort the array so that duplicate values become adjacent. sort(arr.begin(), arr.end()); int answer = arr[0]; int maxFrequency = 0; int start = 0; // Process one group of equal elements at a time. while (start < arr.size()) { int end = start; // Extend the current group while the values remain the same. while (end < arr.size() && arr[end] == arr[start]) { end++; } // Calculate the size of the current group. int currentFrequency = end - start; int currentValue = arr[start]; /* Update the answer if the current element has a higher frequency or wins the tie-break. */ if (currentFrequency > maxFrequency || (currentFrequency == maxFrequency && currentValue < answer)) { maxFrequency = currentFrequency; answer = currentValue; } // Move to the beginning of the next group. start = end; } return answer; }};// Driver Code startsint main() { vector<int> arr = {4, 1, 4, 2, 1}; Solution solution; // Call the function to find the most frequent element. int answer = solution.mostFrequentElement(arr); cout << answer << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N log(N)), where N is the size of the array. The sorting operation takes O(N log(N)) time and dominates the overall complexity.
Space Complexity: O(1), because any extra space is not used.
Optimal Approach
In the previous approach, sorting helped us to place the elements in order. But sorting is not really necessary. The only thing needed is the frequency of every element.
While traversing the array the frequency of each element can be stored and updated in a hash map. Whenever a higher frequency is found, the answer is updated. If two elements have the same frequency, the smaller one is chosen.
Algorithm
If the array is empty, the answer is -1 because no element is present.
While traversing the array the frequency of every element is stored in a hash map.
As the frequency of each element is updated, the highest frequency found so far is also checked.
Whenever a higher frequency is found, the answer is updated to that element.
If another element has the same frequency, the smaller one is kept as the answer.
Dry Run
Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns the most frequent element in the array. int mostFrequentElement(const vector<int>& arr) { // If the array is empty, there is no answer. if (arr.empty()) { return -1; } unordered_map<int, int> frequency; int answer = arr[0]; int maxFrequency = 0; // Count the frequency of every element. for (int value : arr) { // Increase the frequency of the current element. int currentFrequency = ++frequency[value]; /* Update the answer if the current element has a higher frequency or wins the tie-break. */ if (currentFrequency > maxFrequency || (currentFrequency == maxFrequency && value < answer)) { maxFrequency = currentFrequency; answer = value; } } return answer; }};// Driver Code startsint main() { vector<int> arr = {4, 1, 4, 2, 1}; Solution solution; // Call the function to find the most frequent element. int answer = solution.mostFrequentElement(arr); cout << answer << "\n"; return 0;}Complexity Analysis
Time Complexity: O(N) on average, where N is the number of elements in the array, because every element is processed once and each hash-map update takes average O(1) time. In the worst-case scenario, frequent collisions can significantly slow down operations.
Space Complexity: O(K), where K is the number of distinct values stored in the frequency map. At the worst-case the hash-map can contain all the N elements, so worst case space complexity is O(N).
Interview follow-up Questions
No. A majority element must occur more than n / 2 times. The most frequent element is simply the element that appears more no of times than any other element. It does not have to appear more than half the time.
Be the first to add a comment.