Open In App

Most frequent element in an array

Last Updated : 11 Jan, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Given an array, find the most frequent element in it. If there are multiple elements that appear a maximum number of times, print any one of them.

Examples: 

Input : arr[] = {1, 3, 2, 1, 4, 1}
Output : 1
Explanation: 1 appears three times in array which is maximum frequency.

Input : arr[] = {10, 20, 10, 20, 30, 20, 20}
Output : 20

A simple solution is to run two loops. The outer loop picks all elements one by one. The inner loop finds the frequency of the picked element and compares it with the maximum so far. 

Implementation:

C++




// CPP program to find the most frequent element
// in an array.
#include <bits/stdc++.h>
using namespace std;
  
int mostFrequent(int* arr, int n)
{
    // code here
    int maxcount = 0;
    int element_having_max_freq;
    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_having_max_freq = arr[i];
        }
    }
  
    return element_having_max_freq;
}
  
// Driver program
int main()
{
    int arr[] = { 40, 50, 30, 40, 50, 30, 30 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << mostFrequent(arr, n);
    return 0;
}
  
// This code is contributed by Arpit Jain


Java




public class GFG
{
    
  // Java program to find the most frequent element
  // in an array.
  public static int mostFrequent(int[] arr, int n)
  {
    int maxcount = 0;
    int element_having_max_freq = 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_having_max_freq = arr[i];
      }
    }
  
    return element_having_max_freq;
  }
  
  // Driver program
  public static void main(String[] args)
  {
    int[] arr = { 40, 50, 30, 40, 50, 30, 30 };
    int n = arr.length;
    System.out.print(mostFrequent(arr, n));
  }
}
  
// This code is contributed by Aarti_Rathi


Python3




# Python3 program to find the most
# frequent element in an array.
def mostFrequent(arr, n):
  maxcount = 0;
  element_having_max_freq = 0;
  for i in range(0, n):
    count = 0
    for j in range(0, n):
      if(arr[i] == arr[j]):
        count += 1
    if(count > maxcount):
      maxcount = count
      element_having_max_freq = arr[i]
    
  return element_having_max_freq;
  
# Driver Code
arr = [40,50,30,40,50,30,30]
n = len(arr)
print(mostFrequent(arr, n))
  
# This code is contributed by Arpit Jain


C#




// C# program to find the most frequent element
// in an array
using System;
public class GFG
{
    
  // C# program to find the most frequent element
  // in an array.
  public static int mostFrequent(int[] arr, int n)
  {
    int maxcount = 0;
    int element_having_max_freq = 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_having_max_freq = arr[i];
      }
    }
  
    return element_having_max_freq;
  }
  
  // Driver program
  public static void Main(String[] args)
  {
    int[] arr = { 40, 50, 30, 40, 50, 30, 30 };
    int n = arr.Length;
    Console.Write(mostFrequent(arr, n));
  }
}
  
// This code is contributed by Abhijeet Kumar(abhijeet19403)


Javascript




// JavaScript program to find the most frequent element in an array
function mostFrequent(arr, n) {
 
    let maxcount = 0;
    let element_having_max_freq;
    for (let i = 0; i < n; i++) {
        let count = 0;
        for (let j = 0; j < n; j++) {
            if (arr[i] == arr[j])
                count++;
        }
 
        if (count > maxcount) {
            maxcount = count;
            element_having_max_freq = arr[i];
        }
    }
 
    return element_having_max_freq;
}
 
// Driver Code
 
let arr = [40, 50, 30, 40, 50, 30, 30];
let n = arr.length;
console.log(mostFrequent(arr, n));


Output

30

The time complexity of this solution is O(n2) since 2 loops are running from i=0 to i=n we can improve its time complexity by taking a visited  array and skipping numbers for which we already calculated the frequency.
Auxiliary space: O(1) as it is using constant space for variables

A better solution is to do the sorting. We first sort the array, then linearly traverse the array. 

Implementation: 

C++




// CPP program to find the most frequent element
// in an array.
#include <bits/stdc++.h>
using namespace std;
  
int mostFrequent(int arr[], int n)
{
    // Sort the array
    sort(arr, arr + n);
  
    // Find the max frequency using linear traversal
    int max_count = 1, res = arr[0], curr_count = 1;
    for (int i = 1; i < n; i++) {
        if (arr[i] == arr[i - 1])
            curr_count++;
        else
            curr_count = 1;
        
        if (curr_count > max_count) {
            max_count = curr_count;
            res = arr[i - 1];
        }
    }
  
    return res;
}
  
// Driver program
int main()
{
    int arr[] = { 40,50,30,40,50,30,30};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << mostFrequent(arr, n);
    return 0;
}
  
// This code is contributed by Aditya Kumar (adityakumar129)


C




// CPP program to find the most frequent element
// in an array.
#include <stdio.h>
#include <stdlib.h>
  
int cmpfunc(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}
  
int mostFrequent(int arr[], int n)
{
    // Sort the array
    qsort(arr, n, sizeof(int), cmpfunc);
  
    // find the max frequency using linear traversal
    int max_count = 1, res = arr[0], curr_count = 1;
     for (int i = 1; i < n; i++) {
        if (arr[i] == arr[i - 1])
            curr_count++;
        else
            curr_count = 1;
        
        if (curr_count > max_count) {
            max_count = curr_count;
            res = arr[i - 1];
        }
    }
    
    return res;
}
  
// driver program
int main()
{
    int arr[] = { 40,50,30,40,50,30,30};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("%d", mostFrequent(arr, n));
    return 0;
}
  
// This code is contributed by Aditya Kumar (adityakumar129)


Java




// Java program to find the most frequent element
// in an array
import java.util.*;
  
class GFG {
  
    static int mostFrequent(int arr[], int n)
    {
        // Sort the array
        Arrays.sort(arr);
  
        // find the max frequency using linear traversal
        int max_count = 1, res = arr[0];
        int curr_count = 1;
  
        for (int i = 1; i < n; i++) {
            if (arr[i] == arr[i - 1])
                curr_count++;
            else
                curr_count = 1;
  
            if (curr_count > max_count) {
                max_count = curr_count;
                res = arr[i - 1];
            }
        }
        return res;
    }
  
    // Driver program
    public static void main(String[] args)
    {
        int arr[] = { 40,50,30,40,50,30,30};
        int n = arr.length;
        System.out.println(mostFrequent(arr, n));
    }
}
  
// This code is contributed by Aditya Kumar (adityakumar129)


Python3




# Python3 program to find the most
# frequent element in an array.
  
  
def mostFrequent(arr, n):
  
    # Sort the array
    arr.sort()
  
    # find the max frequency using
    # linear traversal
    max_count = 1
    res = arr[0]
    curr_count = 1
  
    for i in range(1, n):
        if (arr[i] == arr[i - 1]):
            curr_count += 1
        else:
            curr_count = 1
  
         # If last element is most frequent
        if (curr_count > max_count):
            max_count = curr_count
            res = arr[i - 1]
  
    return res
  
  
# Driver Code
arr = [40,50,30,40,50,30,30]
n = len(arr)
print(mostFrequent(arr, n))
  
# This code is contributed by Smitha Dinesh Semwal.


C#




// C# program to find the most
// frequent element in an array
using System;
  
class GFG {
  
    static int mostFrequent(int[] arr, int n)
    {
  
        // Sort the array
        Array.Sort(arr);
  
        // find the max frequency using
        // linear traversal
        int max_count = 1, res = arr[0];
        int curr_count = 1;
  
        for (int i = 1; i < n; i++) {
            if (arr[i] == arr[i - 1])
                curr_count++;
            else
                curr_count = 1;
  
            // If last element is most frequent
            if (curr_count > max_count) {
                max_count = curr_count;
                res = arr[i - 1];
            }
        }
  
        return res;
    }
  
    // Driver code
    public static void Main()
    {
  
        int[] arr = {40,50,30,40,50,30,30 };
        int n = arr.Length;
  
        Console.WriteLine(mostFrequent(arr, n));
    }
}
  
// This code is contributed by vt_m.


PHP




<?php
// PHP program to find the
// most frequent element
// in an array.
  
function mostFrequent( $arr, $n)
{
      
    // Sort the array
    sort($arr);
    sort($arr , $n);
  
    // find the max frequency 
    // using linear traversal
    $max_count = 1; 
    $res = $arr[0]; 
    $curr_count = 1;
    for ($i = 1; $i < $n; $i++) 
    {
        if ($arr[$i] == $arr[$i - 1])
            $curr_count++;
        else
              $curr_count = 1;
         
         if ($curr_count > $max_count)
         {
              $max_count = $curr_count;
              $res = $arr[$i - 1];
          }
    }
  
    return $res;
}
  
// Driver Code
{
    $arr = array(40,50,30,40,50,30,30);
    $n = sizeof($arr) / sizeof($arr[0]);
    echo mostFrequent($arr, $n);
    return 0;
}
  
// This code is contributed by nitin mittal
?>


Javascript




<script>
// JavaScript program to find the most frequent element
//in an array
  
    function mostFrequent(arr, n)
    {
            
        // Sort the array
        arr.sort();
            
        // find the max frequency using linear
        // traversal
        let max_count = 1, res = arr[0];
        let curr_count = 1;
            
        for (let i = 1; i < n; i++)
        {
            if (arr[i] == arr[i - 1])
                curr_count++;
            else
                curr_count = 1;
             
            if (curr_count > max_count)
            {
                max_count = curr_count;
                res = arr[i - 1];
            }
  
        }
          
        return res;
    }
        
// Driver Code
  
        let arr = [40,50,30,40,50,30,30];
        let n = arr.length;
        document.write(mostFrequent(arr,n));
  
// This code is contributed by code_hunt.
</script>


Output

30

Time Complexity: O(nlog(n)) 
Auxiliary Space: O(1)

An efficient solution is to use hashing. We create a hash table and store elements and their frequency counts as key-value pairs. Finally, we traverse the hash table and print the key with the maximum value.  

C++




// CPP program to find the most frequent element
// in an array.
#include <bits/stdc++.h>
using namespace std;
  
int mostFrequent(int arr[], int n)
{
    // Insert all elements in hash.
    unordered_map<int, int> hash;
    for (int i = 0; i < n; i++)
        hash[arr[i]]++;
  
    // find the max frequency
    int max_count = 0, res = -1;
    for (auto i : hash) {
        if (max_count < i.second) {
            res = i.first;
            max_count = i.second;
        }
    }
  
    return res;
}
  
// driver program
int main()
{
    int arr[] = {40,50,30,40,50,30,30 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << mostFrequent(arr, n);
    return 0;
}


Java




//Java program to find the most frequent element
//in an array
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;
  
class GFG {
      
    static int mostFrequent(int arr[], int n)
    {
          
        // Insert all elements in hash
        Map<Integer, Integer> hp =
               new HashMap<Integer, Integer>();
          
        for(int i = 0; i < n; i++)
        {
            int key = arr[i];
            if(hp.containsKey(key))
            {
                int freq = hp.get(key);
                freq++;
                hp.put(key, freq);
            }
            else
            {
                hp.put(key, 1);
            }
        }
          
        // find max frequency.
        int max_count = 0, res = -1;
          
        for(Entry<Integer, Integer> val : hp.entrySet())
        {
            if (max_count < val.getValue())
            {
                res = val.getKey();
                max_count = val.getValue();
            }
        }
          
        return res;
    }
      
    // Driver code
    public static void main (String[] args) {
          
        int arr[] = {40,50,30,40,50,30,30};
        int n = arr.length;
          
        System.out.println(mostFrequent(arr, n));
    }
}
  
// This code is contributed by Akash Singh.


Python3




# Python3 program to find the most 
# frequent element in an array.
import math as mt
  
def mostFrequent(arr, n):
  
    # Insert all elements in Hash.
    Hash = dict()
    for i in range(n):
        if arr[i] in Hash.keys():
            Hash[arr[i]] += 1
        else:
            Hash[arr[i]] = 1
  
    # find the max frequency
    max_count = 0
    res = -1
    for i in Hash
        if (max_count < Hash[i]): 
            res = i
            max_count = Hash[i]
          
    return res
  
# Driver Code
arr = [ 40,50,30,40,50,30,30
n = len(arr)
print(mostFrequent(arr, n))
  
# This code is contributed 
# by Mohit kumar 29


C#




// C# program to find the most 
// frequent element in an array
using System;
using System.Collections.Generic;
  
class GFG
{
    static int mostFrequent(int []arr, 
                            int n)
    {
        // Insert all elements in hash
        Dictionary<int, int> hp = 
                    new Dictionary<int, int>();
          
        for (int i = 0; i < n; i++)
        {
            int key = arr[i];
            if(hp.ContainsKey(key))
            {
                int freq = hp[key];
                freq++;
                hp[key] = freq;
            }
            else
                hp.Add(key, 1);
        }
          
        // find max frequency.
        int min_count = 0, res = -1;
          
        foreach (KeyValuePair<int
                    int> pair in hp)
        {
            if (min_count < pair.Value)
            {
                res = pair.Key;
                min_count = pair.Value;
            }
        
        return res;
    }
      
    // Driver code
    static void Main ()
    {
        int []arr = new int[]{40,50,30,40,50,30,30};
        int n = arr.Length;
          
        Console.Write(mostFrequent(arr, n));
    }
}
  
// This code is contributed by
// Manish Shaw(manishshaw1)


Javascript




<script>
  
// Javascript program to find
// the most frequent element
// in an array.
  
function mostFrequent(arr, n)
{
    // Insert all elements in hash.
    var hash = new Map();
    for (var i = 0; i < n; i++)
    {
        if(hash.has(arr[i]))
            hash.set(arr[i], hash.get(arr[i])+1)
        else
            hash.set(arr[i], 1)
    }
  
    // find the max frequency
    var max_count = 0, res = -1;
    hash.forEach((value,key) => {
          
        if (max_count < value) {
            res = key;
            max_count = value;
        }
  
    });
  
    return res;
}
  
// driver program
var arr = [40,50,30,40,50,30,30];
var n = arr.length;
document.write( mostFrequent(arr, n));
  
</script>


Output

30

Time Complexity: O(n) 
Auxiliary Space: O(n)

An efficient solution to this problem can be to solve this problem by Moore’s voting Algorithm.

NOTE: THE ABOVE VOTING ALGORITHM ONLY WORKS WHEN THE MAXIMUM OCCURRING ELEMENT IS MORE THAN (SIZEOFARRAY/2) TIMES;

In this method, we will find the maximum occurred integer by counting the votes a number has.

C++




#include <iostream>
using namespace std;
  
int maxFreq(int *arr, int n) {
    //using moore's voting algorithm
    int res = 0;
    int count = 1;
    for(int i = 1; i < n; i++) {
        if(arr[i] == arr[res]) {
            count++;
        } else {
            count--;
        }
          
        if(count == 0) {
            res = i;
            count = 1;
        }
          
    }
      
    return arr[res];
}
  
int main()
{
    int arr[] = {40,50,30,40,50,30,30};
    int n = sizeof(arr) / sizeof(arr[0]);
    int freq =  maxFreq(arr , n);
    int count = 0;
    for(int i = 0; i < n; i++) {
        if(arr[i] == freq) {
            count++;
        }
    }
    cout <<"Element " << maxFreq(arr , n) << " occurs " << count << " times" << endl;; 
    return 0;
    //This code is contributed by Ashish Kumar Shakya
}


Java




import java.io.*;
class GFG
{
  
static int maxFreq(int []arr, int n) 
{
    
    // using moore's voting algorithm
    int res = 0;
    int count = 1;
    for(int i = 1; i < n; i++) {
        if(arr[i] == arr[res]) {
            count++;
        } else {
            count--;
        }
          
        if(count == 0) {
            res = i;
            count = 1;
        }
          
    }
      
    return arr[res];
}
  
  // Driver code
public static void main (String[] args) {
    int arr[] = {40,50,30,40,50,30,30};
    int n = arr.length;
    int freq =  maxFreq(arr , n);
    int count = 0;
    for(int i = 0; i < n; i++) {
        if(arr[i] == freq) {
            count++;
        }
    }
    System.out.println("Element " +maxFreq(arr , n) +" occurs "  +count +" times" ); 
}
      
}
  
// This code is contributed by shivanisinghss2110


Python3




def maxFreq(arr, n):
      
    # Using moore's voting algorithm
    res = 0
    count = 1
      
    for i in range(1, n):
        if (arr[i] == arr[res]):
            count += 1
        else:
            count -= 1
          
        if (count == 0):
            res = i
            count = 1
          
    return arr[res]
  
# Driver code
arr = [ 40, 50, 30, 40, 50, 30, 30 ]
n = len(arr)
freq =  maxFreq(arr, n)
count = 0
  
for i in range (n):
        if(arr[i] == freq):
            count += 1
          
print("Element ", maxFreq(arr , n), 
      " occurs ", count, " times")
  
# This code is contributed by shivanisinghss2110


C#




using System;
class GFG
{
  
static int maxFreq(int []arr, int n) 
{
    
    // using moore's voting algorithm
    int res = 0;
    int count = 1;
    for(int i = 1; i < n; i++) {
        if(arr[i] == arr[res]) {
            count++;
        } else {
            count--;
        }
          
        if(count == 0) {
            res = i;
            count = 1;
        }
          
    }
      
    return arr[res];
}
  
  // Driver code
public static void Main (String[] args) {
    int []arr = {40,50,30,40,50,30,30};
    int n = arr.Length;
    int freq =  maxFreq(arr , n);
    int count = 0;
    for(int i = 0; i < n; i++) {
        if(arr[i] == freq) {
            count++;
        }
    }
    Console.Write("Element " +maxFreq(arr , n) +" occurs "  +count +" times" ); 
}
      
}
  
// This code is contributed by shivanisinghss2110


Javascript




<script>
  
      function maxFreq(arr, n) {
        //using moore's voting algorithm
        var res = 0;
        var count = 1;
        for (var i = 1; i < n; i++) {
          if (arr[i] === arr[res]) {
            count++;
          } else {
            count--;
          }
  
          if (count === 0) {
            res = i;
            count = 1;
          }
        }
  
        return arr[res];
      }
  
      var arr = [40, 50, 30, 40, 50, 30, 30];
      var n = arr.length;
      var freq = maxFreq(arr, n);
      var count = 0;
      for (var i = 0; i < n; i++) {
        if (arr[i] === freq) {
          count++;
        }
      }
      document.write(
        "Element " + maxFreq(arr, n) + " occurs "
        count + " times" + "<br>"
      );
        
</script>


Output

Element 30 occurs 3 times

Time Complexity: O(n)
Auxiliary Space: O(1)



Previous Article
Next Article

Similar Reads

Minimum distance between any most frequent and least frequent element of an array
Given an integer array arr[] of size N, the task is to find the minimum distance between any most and least frequent element of the given array. Examples: Input: arr[] = {1, 1, 2, 3, 2, 3, 3}Output: 1Explanation: The least frequent elements are 1 and 2 which occurs at indexes: 0, 1, 2, 4. Whereas, the most frequent element is 3 which occurs at inde
13 min read
Check if most frequent element in Linked list is divisible by smallest element
Given a Linked list, the task is to check if the most frequently occurring element in the linked list is divisible by the smallest element in the linked list. If divisible then return true otherwise return false. Note: If there is more than one mode then take the greater mode. Examples: Input: Linked List: 4 -&gt; 2 -&gt; 1 -&gt; 3 -&gt; 3 -&gt; 3O
7 min read
Generate an array consisting of most frequent greater elements present on the right side of each array element
Given an array A[] of size N, the task is to generate an array B[] based on the following conditions: For every array element A[i], find the most frequent element greater than A[i] present on the right of A[i]. Insert that element into B[].If more than one such element is present on the right, choose the element having the smallest value.If no elem
9 min read
Most frequent element in Array after replacing given index by K for Q queries
Given an array arr[] of size N, and Q queries of the form {i, k} for which, the task is to print the most frequent element in the array after replacing arr[i] by k.Example : Input: arr[] = {2, 2, 2, 3, 3}, Query = {{0, 3}, {4, 2}, {0, 4}} Output: 3 2 2 First query: Setting arr[0] = 3 modifies arr[] = {3, 2, 2, 3, 3}. So, 3 has max frequency. Second
10 min read
Remove an occurrence of most frequent array element exactly K times
Given an array arr[], the task is to remove an occurrence of the most frequent array element exactly K times. If multiple array elements have maximum frequency, remove the smallest of them. Print the K deleted elements. Examples: Input: arr[] = {1, 3, 2, 1, 4, 1}, K = 2Output: 1 1Explanation: The frequency of 1 is 3 and frequencies of 2, 3, 4 are 1
12 min read
Find the most frequent element K positions apart from X in given Array
Given an array nums[], and integer K and X, the task is to find the most frequent element K positions away from X in the given array. Examples: Input: nums = [1, 100, 200, 1, 100], K = 1, X = 1Output: 100Explanation: Elements 1 position apart from 1 is only 100.So the answer is 100. Input: nums = [2, 2, 2, 2, 3], K = 2, X = 2Output: X = 2 occurs in
6 min read
Find given occurrences of Mth most frequent element of Array
Given an array arr[], integer M and an array query[] containing Q queries, the task is to find the query[i]th occurrence of Mth most frequent element of the array. Examples: Input: arr[] = {1, 2, 20, 8, 8, 1, 2, 5, 8, 0, 6, 8, 2}, M = 1, query[] = {100, 4, 2}Output: -1, 12, 5Explanation: Here most frequent Integer = 8, with frequency = 4Thus for Qu
9 min read
Queries to insert, delete one occurrence of a number and print the least and most frequent element
Given Q queries of type 1, 2, 3 and 4 as described below. Type-1: Insert a number to the list.Type-2: Delete only one occurrence of a number if exists.Type-3: Print the least frequent element, if multiple elements exist then print the greatest among them.Type-4: Print the most frequent element, if multiple elements exist then print the smallest amo
14 min read
Count of subarrays with X as the most frequent element, for each value of X from 1 to N
Given an array arr[] of size N, (where 0&lt;A[i]&lt;=N, for all 0&lt;=i&lt;N), the task is to calculate for each number X from 1 to N, the number of subarrays in which X is the most frequent element. In subarrays, where more than one element has the maximum frequency, the smallest element should be considered as the most frequent. Examples: Input:
7 min read
Smallest subarray with all occurrences of a most frequent element
Given an array, A. Let x be an element in the array. x has the maximum frequency in the array. Find the smallest subsegment of the array which also has x as the maximum frequency element. Examples: Input : arr[] = {4, 1, 1, 2, 2, 1, 3, 3} Output : 1, 1, 2, 2, 1 The most frequent element is 1. The smallest subarray that has all occurrences of it is
8 min read
Article Tags :
Practice Tags :