Highest occurring element in an array
Beginner Problems
Basic Hashing
Easy
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.
Please note that this section might seem a bit difficult without prior knowledge on what hashing is, we will soon try to add basics concepts for your ease! If you know the concepts already please go ahead to give a shot to the problem. Cheers!
Examples:
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.
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.
Input: arr = [10, 9 ,7]
Constraints
- 1 <= n <= 105
- 1 <= arr[i] <= 104
Company Tags
TCS
Cognizant
Accenture
Infosys
Capgemini
Wipro
IBM
HCL
Tech Mahindra
MindTree
Editorial
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:
Solution:
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to get the highest
occurring element in array nums */
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;
// Visited array
vector<bool> visited(n, false);
// First loop
for(int i = 0; i < n; i++) {
// Skip second loop if already visited
if(visited[i]) continue;
/* Variable to store frequency
of current element */
int freq = 0;
// Second loop
for(int j = i; j < n; j++) {
if(nums[i] == nums[j]) {
freq++;
visited[j] = true;
}
}
/* Update variables if new element having
highest frequency is found */
if(freq > maxFreq) {
maxFreq = freq;
maxEle = nums[i];
} else if(freq == maxFreq) {
maxEle = min(maxEle, nums[i]);
}
}
// Return the result
return maxEle;
}
};
int main() {
vector<int> nums = {4, 4, 5, 5, 6};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to get the
highest occurring element in array nums */
int ans = sol.mostFrequentElement(nums);
cout << "The highest occurring element in the array is: " << ans;
return 0;
}
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566
import java.util.*;
class Solution {
/* Function to get the highest
occurring element in array nums */
public int mostFrequentElement(int[] nums) {
// Variable to store the size of array
int n = nums.length;
// Variable to store maximum frequency
int maxFreq = 0;
/* Variable to store element
with maximum frequency */
int maxEle = 0;
// Visited array
boolean[] visited = new boolean[n];
// First loop
for (int i = 0; i < n; i++) {
// Skip second loop if already visited
if (visited[i]) continue;
/* Variable to store frequency
of current element */
int freq = 0;
// Second loop
for (int j = i; j < n; j++) {
if (nums[i] == nums[j]) {
freq++;
visited[j] = true;
}
}
/* Update variables if new element having
highest frequency is found */
if (freq > maxFreq) {
maxFreq = freq;
maxEle = nums[i];
} else if (freq == maxFreq) {
maxEle = Math.min(maxEle, nums[i]);
}
}
// Return the result
return maxEle;
}
public static void main(String[] args) {
int[] nums = {4, 4, 5, 5, 6};
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to get the
highest occurring element in array nums */
int ans = sol.mostFrequentElement(nums);
System.out.println("The highest occurring element in the array is: " + ans);
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
class Solution:
# Function to get the highest
# occurring element in array nums
def mostFrequentElement(self, nums):
# Variable to store the size of array
n = len(nums)
# Variable to store maximum frequency
maxFreq = 0
# Variable to store element
# with maximum frequency
maxEle = 0
# Visited array
visited = [False] * n
# First loop
for i in range(n):
# Skip second loop if already visited
if visited[i]:
continue
# Variable to store frequency
# of current element
freq = 0
# Second loop
for j in range(i, n):
if nums[i] == nums[j]:
freq += 1
visited[j] = True
# Update variables if new element having
# highest frequency is found
if freq > maxFreq:
maxFreq = freq
maxEle = nums[i]
elif freq == maxFreq:
maxEle = min(maxEle, nums[i])
# Return the result
return maxEle
if __name__ == "__main__":
nums = [4, 4, 5, 5, 6]
# Creating an instance of Solution class
sol = Solution()
# Function call to get the
# highest occurring element in array nums
ans = sol.mostFrequentElement(nums)
print("The highest occurring element in the array is:", ans)1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
class Solution {
/* Function to get the highest
occurring element in array nums */
mostFrequentElement(nums) {
// Variable to store the size of array
let n = nums.length;
// Variable to store maximum frequency
let maxFreq = 0;
/* Variable to store element
with maximum frequency */
let maxEle = 0;
// Visited array
let visited = new Array(n).fill(false);
// First loop
for (let i = 0; i < n; i++) {
// Skip second loop if already visited
if (visited[i]) continue;
/* Variable to store frequency
of current element */
let freq = 0;
// Second loop
for (let j = i; j < n; j++) {
if (nums[i] == nums[j]) {
freq++;
visited[j] = true;
}
}
/* Update variables if new element having
highest frequency is found */
if (freq > maxFreq) {
maxFreq = freq;
maxEle = nums[i];
} else if (freq == maxFreq) {
maxEle = Math.min(maxEle, nums[i]);
}
}
// Return the result
return maxEle;
}
}
// Input array
let nums = [4, 4, 5, 5, 6];
// Creating an instance of Solution class
let sol = new Solution();
/* Function call to get the
highest occurring element in array nums */
let ans = sol.mostFrequentElement(nums);
console.log("The highest occurring element in the array is: " + ans);
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.
Intuition:
An optimal approach to solve this question will be to use 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.
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:
Solution:
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/* Function to get the highest
occuring element in array n */
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;
}
};
int main() {
vector<int> nums = {4, 4, 5, 5, 6};
/* Creating an instance of
Solution class */
Solution sol;
/* Function call to get the
highest occuring element in array n */
int ans = sol.mostFrequentElement(nums);
cout << "The highest occurring element in the array is: " << ans;
return 0;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657
import java.util.*;
class Solution {
/* Function to get the highest
occurring element in array n */
public int mostFrequentElement(int[] nums) {
// Variable to store the size of array
int n = nums.length;
// Variable to store maximum frequency
int maxFreq = 0;
/* Variable to store element
with maximum frequency */
int maxEle = 0;
// HashMap
Map<Integer, Integer> mpp = new HashMap<>();
// Iterating on the array
for (int i = 0; i < n; i++) {
// Updating hashmap
mpp.put(nums[i], mpp.getOrDefault(nums[i], 0) + 1);
}
// Iterate on the map
for (Map.Entry<Integer, Integer> it : mpp.entrySet()) {
int ele = it.getKey(); // Key
int freq = it.getValue(); // Value
if (freq > maxFreq) {
maxFreq = freq;
maxEle = ele;
} else if (freq == maxFreq) {
maxEle = Math.min(maxEle, ele);
}
}
// Return the result
return maxEle;
}
public static void main(String[] args) {
int[] nums = {4, 4, 5, 5, 6};
/* Creating an instance of
Solution class */
Solution sol = new Solution();
/* Function call to get the
highest occurring element in array n */
int ans = sol.mostFrequentElement(nums);
System.out.println("The highest occurring element in the array is: " + ans);
}
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748
class Solution:
# Function to get the highest
# occurring element in array n
def mostFrequentElement(self, nums):
# Variable to store the size of array
n = len(nums)
# Variable to store maximum frequency
maxFreq = 0
# Variable to store element
# with maximum frequency
maxEle = 0
# HashMap
mpp = {}
# Iterating on the array
for num in nums:
# Updating hashmap
if num in mpp:
mpp[num] += 1
else:
mpp[num] = 1
# Iterate on the map
for ele, freq in mpp.items():
if freq > maxFreq:
maxFreq = freq
maxEle = ele
elif freq == maxFreq:
maxEle = min(maxEle, ele)
# Return the result
return maxEle
# Input array
nums = [4, 4, 5, 5, 6]
# Creating an instance of Solution class
sol = Solution()
# Function call to get the highest
# occurring element in array n
ans = sol.mostFrequentElement(nums)
print(f"The highest occurring element in the array is: {ans}")123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051
class Solution {
/* Function to get the highest
occurring element in array n */
mostFrequentElement(nums) {
// Variable to store the size of array
let n = nums.length;
// Variable to store maximum frequency
let maxFreq = 0;
// Variable to store element
// with maximum frequency
let maxEle = 0;
// HashMap
let mpp = new Map();
// Iterating on the array
for (let i = 0; i < n; i++) {
// Updating hashmap
mpp.set(nums[i], (mpp.get(nums[i]) || 0) + 1);
}
// Iterate on the map
for (let [ele, freq] of mpp) {
if (freq > maxFreq) {
maxFreq = freq;
maxEle = ele;
} else if (freq === maxFreq) {
maxEle = Math.min(maxEle, ele);
}
}
// Return the result
return maxEle;
}
}
// Input array
let nums = [4, 4, 5, 5, 6];
/* Creating an instance of
Solution class */
let sol = new Solution();
/* Function call to get the
highest occurring element in array n */
let ans = sol.mostFrequentElement(nums);
console.log(`The highest occurring element in the array is: ${ans}`);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.
Notes
Code
✅ Testcase
Input: {'nums': '[1, 2, 2, 3, 3, 3]'}
Expected:
3
3
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[4, 4, 5, 5, 6]'}
Expected:
4
4
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[10, 9 ,7]'}
Expected:
7
7
Actual: -
Time: -
sec
Status: Waiting
Facts
- • The underlying concept of this problem is extensively used in data analytics, specifically in areas requiring analysis of user behaviour
- • For example, music streaming apps often need to find the most frequently listened song among a pool of users
- • In this case, the 'array of n integers' could represent users' song preferences and the 'most frequent element' would be the most popular song
- • Furthermore, finding the 'smallest of them' could be analogous to identifying the most popular song with the shortest duration, which could influence decisions in areas like marketing or content curation