# Most frequent element in an array

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

Examples:

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

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

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

A simple solution is to run two loops. The outer loop picks all elements one by one. The inner loop finds frequency of the picked element and compares with the maximum so far. Time complexity of this solution is O(n2)

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

## C++

 `// CPP program to find the most frequent element ` `// in an array. ` `#include ` `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` `{ ` `            ``if` `(curr_count > max_count) { ` `                ``max_count = curr_count; ` `                ``res = arr[i - 1]; ` `            ``} ` `            ``curr_count = 1; ` `        ``} ` `    ``} ` ` `  `    ``// If last element is most frequent ` `    ``if` `(curr_count > max_count) ` `    ``{ ` `        ``max_count = curr_count; ` `        ``res = arr[n - 1]; ` `    ``} ` ` `  `    ``return` `res; ` `} ` ` `  `// driver program ` `int` `main() ` `{ ` `    ``int` `arr[] = { 1, 5, 2, 1, 3, 2, 1 }; ` `    ``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.*; ` ` `  `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`  `            ``{ ` `                ``if` `(curr_count > max_count) ` `                ``{ ` `                    ``max_count = curr_count; ` `                    ``res = arr[i - ``1``]; ` `                ``} ` `                ``curr_count = ``1``; ` `            ``} ` `        ``} ` `     `  `        ``// If last element is most frequent ` `        ``if` `(curr_count > max_count) ` `        ``{ ` `            ``max_count = curr_count; ` `            ``res = arr[n - ``1``]; ` `        ``} ` `     `  `        ``return` `res; ` `    ``} ` `     `  `    ``// Driver program ` `    ``public` `static` `void` `main (String[] args) { ` `         `  `        ``int` `arr[] = {``1``, ``5``, ``2``, ``1``, ``3``, ``2``, ``1``}; ` `        ``int` `n = arr.length; ` `         `  `        ``System.out.println(mostFrequent(arr,n)); ` `         `  `    ``} ` `} ` ` `  `// This code is contributed by Akash Singh. `

/div>

## 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` `: ` `            ``if` `(curr_count > max_count):  ` `                ``max_count ``=` `curr_count ` `                ``res ``=` `arr[i ``-` `1``] ` `             `  `            ``curr_count ``=` `1` `     `  `    ``# If last element is most frequent ` `    ``if` `(curr_count > max_count): ` `     `  `        ``max_count ``=` `curr_count ` `        ``res ``=` `arr[n ``-` `1``] ` `     `  `    ``return` `res ` ` `  `# Driver Code ` `arr ``=` `[``1``, ``5``, ``2``, ``1``, ``3``, ``2``, ``1``]  ` `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` `            ``{ ` `                ``if` `(curr_count > max_count) ` `                ``{ ` `                    ``max_count = curr_count; ` `                    ``res = arr[i - 1]; ` `                ``} ` `                ``curr_count = 1; ` `            ``} ` `        ``} ` `     `  `        ``// If last element is most frequent ` `        ``if` `(curr_count > max_count) ` `        ``{ ` `            ``max_count = curr_count; ` `            ``res = arr[n - 1]; ` `        ``} ` `     `  `        ``return` `res; ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `Main ()  ` `    ``{ ` `         `  `        ``int` `[]arr = {1, 5, 2, 1, 3, 2, 1}; ` `        ``int` `n = arr.Length; ` `         `  `        ``Console.WriteLine(mostFrequent(arr,n)); ` `         `  `    ``} ` `} ` ` `  `// This code is contributed by vt_m. `

## PHP

 ` ``\$max_count``) ` `            ``{ ` `                ``\$max_count` `= ``\$curr_count``; ` `                ``\$res` `= ``\$arr``[``\$i` `- 1]; ` `            ``} ` `            ``\$curr_count` `= 1; ` `        ``} ` `    ``} ` ` `  `    ``// If last element  ` `    ``// is most frequent ` `    ``if` `(``\$curr_count` `> ``\$max_count``) ` `    ``{ ` `        ``\$max_count` `= ``\$curr_count``; ` `        ``\$res` `= ``\$arr``[``\$n` `- 1]; ` `    ``} ` ` `  `    ``return` `\$res``; ` `} ` ` `  `// Driver Code ` `{ ` `    ``\$arr` `= ``array``(1, 5, 2, 1, 3, 2, 1); ` `    ``\$n` `= sizeof(``\$arr``) / sizeof(``\$arr``[0]); ` `    ``echo` `mostFrequent(``\$arr``, ``\$n``); ` `    ``return` `0; ` `} ` ` `  `// This code is contributed by nitin mittal ` `?> `

Output :

```1
```

Time Complexity : O(n Log 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 maximum value.

## C++

 `// CPP program to find the most frequent element ` `// in an array. ` `#include ` `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[] = { 1, 5, 2, 1, 3, 2, 1 }; ` `    ``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 hp = ` `               ``new` `HashMap(); ` `         `  `        ``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 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[] = {``1``, ``5``, ``2``, ``1``, ``3``, ``2``, ``1``}; ` `        ``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 = [ 1, 5, 2, 1, 3, 2, 1] n = len(arr) print(mostFrequent(arr, n)) # This code is contributed # by Mohit kumar 29 [tabby title="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``[]{1, 5, 2,  ` `                              ``1, 3, 2, 1}; ` `        ``int` `n = arr.Length; ` `         `  `        ``Console.Write(mostFrequent(arr, n)); ` `    ``} ` `} ` ` `  `// This code is contributed by ` `// Manish Shaw(manishshaw1) `

Output:

```1
```

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

## tags:

Hash Searching Sorting Searching Hash Sorting

code