Most Frequent Element in an Array

Problem Description

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.

Example:

Input: [1, 3, 2, 1, 4, 1]
Output: 1
Explanation: 1 appears three times in an array which is maximum frequency

Input: [10, 20, 10, 20, 30, 20, 20]
Output: 20

Solutions

Brute Force

A simple way of solving the problem 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 with the maximum so far.

Due to the two loops, the time complexity would be O(n^2).

Sorting

By sorting an array, we now can traverse an array linearly. Due to the sorting, the time complexity now should be O(nlogn).

Hash Table

An efficient way is to do hashing. We can create a hash table and store elements and their frequency count as key-value pairs. In the end of the day, we just need to traverse the hash table and print the key with maximum value.

The time complexity should be O(n).

Pseudo code in Python

def most_frequent(given_array):
    max_count = -1
    max_item = null
    count = {}  // empty hash table or dictionary
    for item in given_array:
        if item not in count:
            count[item] = 1
        else
            count[item] += 1
        if count[item] > max_count:
            max_count = count[item]
            max_item = item
    return max_item