Problem Statement
Given an array of n integers, find the most frequent element in it i.e., the element that occurs the maximum number of times. If there are multiple elements that appear a maximum number of times, find the smallest of them.
Examples:
Example 1
Input: arr = [1, 2, 2, 3, 3, 3]
Output: 3
Explanation: The number 3 appears the most (3 times). It is the most frequent element.Example 2
Input: arr = [4, 4, 5, 5, 6]
Output: 4
Explanation: Both 4 and 5 appear twice, but 4 is smaller. So, 4 is the most frequent element.Example 3
Input: arr = [10, 9, 7]
Output = 7
Explanation: All elements have the frequency of 1. However, 7 is the smallest among them.Constraints:
1 <= n <= 105
1 <= arr[i] <= 104Different Approaches
Brute Force Approach:
Intuition:
A brute-force way to solve this problem will be to use two loops:
- First loop to iterate on the array, selecting an element.
- Second loop to traverse the remaining array to find the occurrences of the selected element in the first loop.
Maintain a visited array to mark the elements to keep track of duplicate elements that were already taken into account.
Approach:
- Initialize a visited array of boolean type having size n, where n is the size of the array with all elements set to false. Also, declare the following variables :
maxFreq - to store the frequency of the highest occurring element.
maxEle - to store the highest occurring element in the array. - In the first loop, start iterating on the elements of the array selecting one element at a time.
- In the second loop, iterate on the rest portion of the array and count the frequency (number of occurrences) of the selected element. And every time, the same element is found, mark the corresponding index in the visited array as true.
- If the frequency of the current element is found greater than maxFreq, update maxFreq and maxEle with the new frequency and new element respectively.
- If the frequency of the current element is the same as maxFreq, store the smaller of maxEle and the current element in maxEle.
- Before starting the second loop, check if the element is marked as unvisited. Skip the element if it is visited because its frequency has already been taken into consideration.
Dry Run:
index 0 1 2 3
-------------------------
arr | 1 | 2 | 2 | 2 |
-------------------------
^
|
iCode:
#include <iostream>
using namespace std;
int highestOccurringElement(int arr[], int n) {
int maxCount = 0;
int element = arr[0];
for(int i = 0; i < n; i++) {
int count = 0;
for(int j = 0; j < n; j++) {
if(arr[i] == arr[j]) {
count++;
}
}
if(count > maxCount) {
maxCount = count;
element = arr[i];
}
}
return element;
}
int main() {
int arr[] = {1, 3, 2, 3, 4, 1, 3};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Highest occurring element: " << highestOccurringElement(arr, n) << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(N2)(where N is the size of the array given) – Using two nested loops. - Space Complexity:
O(N)– Using a visited array of size N and a couple of variables.
Using Hashing (Unordered Map)
A more efficient way to solve this problem is by using a hash table (unordered map in C++).
A Hashmap, a data structure that stores key-value pairs.
- Key will denote the element in the array.
- Value will store the frequency of the element in the array.
The idea is to store the frequency of each element in the hash table and then find the element with the maximum frequency.
Approach:
- Take a HashMap to store the int key-value pairs.
- Start iterating on the array.
- If the current element is not present in the HashMap, insert it with a frequency of 1.
- Else, increment the frequency of current element in the HashMap.
- Once the iterations are over, all the elements with their frequencies will be stored in the HashMap. Iterate on the HashMap to find the element with the highest frequency.
Dry Run:
Initially
index 0 1 2 3
-------------------------
arr | 1 | 2 | 2 | 2 |
-------------------------
^
|
i (setting i to the zeroth index of arr)
| |
| |
| |
| |
|_______|
Hashmap (empty Hashmap) (element, frquency)
Iterate all the elements of the arrayFirst Pass
index 0 1 2 3
-------------------------
arr | 1 | 2 | 2 | 2 |
-------------------------
^
|
i (arr[i], is not present in Hashmap,
so add a new element with frequency
1. Increase the value of i.)
| |
| |
| |
| (1, 1) |
|________|
Hashmap (element, frquency)Second Pass
index 0 1 2 3
-------------------------
arr | 1 | 2 | 2 | 2 |
-------------------------
^
|
i (arr[i], is not present in Hashmap,
so, add a new element with frequency
1. Increase the value of i.)
| |
| |
| (2, 1) |
| (1, 1) |
|________|
Hashmap (element, frquency)Third Pass
index 0 1 2 3
-------------------------
arr | 1 | 2 | 2 | 2 |
-------------------------
^
|
i (arr[i], is present in
Hasmap, so increase its
frquency by 1.
Increase the value of i.)
| |
| |
| (2, 2) |
| (1, 1) |
|________|
Hashmap (element, frquency)Fourth Pass
index 0 1 2 3
-------------------------
arr | 1 | 2 | 2 | 2 |
-------------------------
^
|
i (arr[i], is present in
Hasmap, so increase its
frquency by 1.
Increase the value of i.)
| |
| |
| (2, 3) |
| (1, 1) |
|________|
Hashmap (element, frquency)Stop Iterating
i has exceeded the array size so terminate the loopIterate all the elements in the Hashmap and find the element with maximum frequency
Iterate all the elements in the Hashmap and find maxFreqElm
-----
maxFreqElm | |
-----
maxFreq 0
| |
| |
| |
| (2, 3) |
| (1, 1) |
----------For the first entry in HashMap
First Entry
| |
| |
| |
| (2, 3) |
| (1, 1) | <- first entry
----------
freq > maxFreq, so update maxFreq and iterate to next
element
maxFreqElm 1
maxFreq 1For the second entry in HashMap
Second Entry
| |
| |
| |
| (2, 3) | <- second entry
| (1, 1) |
----------
freq > maxFreq, so update maxFreq and iterate to next
element
maxFreqElm 2
maxFreq 3We have reached end of HashMap,
so stop iterating and return 'maxEle'
maxEle = 2Code:
int mostFrequentElement(vector<int> &nums) {
// Variable to store the size of array
int n = nums.size();
// Variable to store maximum frequency
int maxFreq = 0;
/* Variable to store element
with maximum frequency */
int maxEle;
// HashMap
unordered_map<int, int> mpp;
// Iterating on the array
for (int i = 0; i < n; i++) {
// Updating hashmap
mpp[nums[i]]++;
}
// Iterate on the map
for(auto it : mpp) {
int ele = it.first; // Key
int freq = it.second; // Value
if(freq > maxFreq) {
maxFreq = freq;
maxEle = ele;
}
else if(freq == maxFreq) {
maxEle = min(maxEle, ele);
}
}
// Return the result
return maxEle;
}Complexity Analysis
- Time Complexity:
O(N)(where N is the size of the array given) –- Using a single loop, performing insertion, updation opertion on HashMap takes O(1) TC resulting in O(N) TC.
- Iterating on HashMap, will take O(N) in the worst-case
- Space Complexity:
O(N)– In the worst-case scenario, the HashMap will store all the elements in the array when array elements are unique.