Most Frequent Element in an Array

You are given an array of integers. The problem statement says that you have to find out the most frequent element present in an array. If there are multiple values that occurs the maximum number of times, then we have to print any of them.

Example

Input

[1, 4,5,3,1,4,16]

Output

The most Frequent Element is: 1

Explanation

Here, 1 comes 3 times (most frequent element in an array)

Input

[23,12,12,34,23,23]

Output

The most Frequent Element is: 23

Explanation

Here, 23 comes 3 times (most frequent element in an array)

Algorithm

1. Declare a Map.
2. Count and store the frequency of each element of an array into the Map.
3. Set maxCount to 0 and result as the minimum value of Integer.
4. Traverse the map and check:
   1. If maxCount<frequency of array element, if true
      1. Set result to that array element
      2. Set maxCount to the frequency of that element

Explanation for Most Frequent Element in an Array

The question given here says to find out the most frequent element present in an array. Also, we are given that if there are multiple values that occurs the maximum number of times, then we are free to print any of them. The code is traversing the map which will have key and values as an element and their frequency if this condition occurs, then, it is going to print the first maximum frequent number. We will define a function getMostFrequent which will receive the arguments as an array and array’s length. The first thing here is to traverse the array and store and count the frequency of each array element and keep increasing the frequency of each array element.

For that, we will use two values, maxCount and result. Initialize the value of maxCount to 0 and result to the minimum value of Integer. We are going to traverse the map and check if maxCount is less than the frequency of an element, if it is found to be true we will set the value of maxCount to the frequency of element and result to that element.

Let us consider an example:

Example

arr={ 2, 5, 2, 3, 3, 2, 1 }

We’ll traverse the array, count and store the frequencies of each element, after traversing we will have our map like this.

myMap={1:1, 2:3, 3:2, 5:1}

We will traverse the map and take each element and check their frequency if greater than maxCount,

maxCount = 0, result=Integer.MIN_VALUE

• value=1, frequency =1

if maxCount < value.second is true, so update the value of maxCount and result

result = value.first, maxCount = value.second;

result = 1, maxCount = 1

• value=2, frequency =3

if maxCount < value.second is true, so update the value of maxCount and result

result = value.first, maxCount = value.second;

result = 2, maxCount = 3

• value=3 frequcny =2

if maxCount < value.second is false, so it  does nothing.

• value=5 frequcny =1

if maxCount < value.second is false.

We have traversed all the values of map and we have the required output in result and we will return result.

Result =2

Implementation

C++ Program for Most Frequent Element in an Array

#include <bits/stdc++.h>
using namespace std;

int getMostFrequent(int arr[], int n)
{
    unordered_map<int, int> myMap;
    for (int i = 0; i < n; i++)
        myMap[arr[i]]++;

    int maxCount = 0, result = INT_MIN;
    for (auto value : myMap)
    {
        if (maxCount < value.second)
        {
            result = value.first;
            maxCount = value.second;
        }
    }
    return result;
}
int main()
{
    int arr[] = { 2, 5, 2, 3, 3, 2, 1 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMostFrequent(arr, n);
    return 0;
}

2

Java Program for Most Frequent Element in an Array

import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

class mostFrequentElement
{
    public static int getMostFrequent(int arr[], int n)
    {
        Map<Integer, Integer> myMap =new HashMap<Integer, Integer>();

        for(int i = 0; i < n; i++)
        {
            if(myMap.containsKey(arr[i]))
            {
                myMap.put(arr[i], myMap.get(arr[i])+1);
            }
            else
            {
                myMap.put(arr[i], 1);
            }
        }
        int maxCount = 0, result= Integer.MIN_VALUE ;
        for(Entry<Integer, Integer> val : myMap.entrySet())
        {
            if (maxCount < val.getValue())
            {
                result = val.getKey();
                maxCount = val.getValue();
            }
        }
        return result;
    }
    public static void main (String[] args)
    {
        int arr[] = { 2, 5, 2, 3, 3, 2, 1 };
        int n = arr.length;
        System.out.println(getMostFrequent(arr, n));
    }
} 

2

Complexity Analysis for Most Frequent Element in an Array

Time Complexity

O(n) where “n” is the number of elements in the array.

Space Complexity

O(n) where “n” is the number of elements in the array.

References