Find Most Frequent Element in an Array

Difficulty: Easy, Asked-in: Facebook, Uber

Key takeaway: This is an excellent problem to learn problem-solving and time complexity optimization using sorting and hash tables.

Let's understand the problem

Given an array X[] of size n, write a program to find the most frequent element in the array, i.e., the element that occurs the maximum number of times.

• It is assumed that at least one element is repeated.
• If there are multiple elements with the maximum frequency, return the smallest of them.

Example 1

Input: X[] = [2, 12, 1, 2, 8, 2, 2, 1, 8, 2], Output: 2

Explanation: 2 is the most frequent element, which appears 4 times.

Example 2

Input: X[] = [1, 9, 1, 1, 2], Output: 1

Explanation: 1 is a single repeated element that appears 3 times.

Example 3

Input: X[] = [3, 8, 2, 3, 2], Output: 2

Explanation: 2 and 3 are repeated two times each, and then we return the smallest of them, which is 2.

Discussed solution approaches

• Brute force approach using nested loops
• Using sorting and linear scan
• Using hash table to store the frequency count

Brute force approach using nested loops

Solution idea and steps

The basic idea is to count the occurrences of each element and return the element with the maximum number of occurrences. We can achieve this using a nested loop where we pick each element using the outer loop and scan the entire array to count the frequency using the inner loop. Here are the solution steps:

Step 1: We initialize two variables outside the nested loops: maxFreq to track the maximum frequency and mostFrequent to track the most frequent element. We set maxFreq to 0 and mostFrequent to -1.

Step 2: We run the outer loop from i = 0 to n - 1 and the inner loop from j = i to n - 1 to count the frequency. Before starting the inner loop, we also initialize a variable countFreq to track the frequency count of each element, i.e. countFreq = 1.

• Inside the inner loop, when we find X[i] = X[j], we increase the value of countFreq by one and move to the next iteration of the inner loop.
• By the end of the inner loop, if maxFreq < countFreq, we found an element X[i] with a frequency greater than the maximum frequency count till that point. So we update maxFreq with countFreq and mostFrequent with X[i].
• If countFreq == maxFreq, we update mostFrequent with the minimum of mostFrequent and X[i], i.e. min(mostFrequent, X[i]).

Step 3: By the end of the nested loop, we return the value stored in mostFrequent.

Solution code C++

int mostFrequentElement(int X[], int n)
{
    int maxFreq = 0;
    int mostFrequent = -1;
    for (int i = 0; i < n; i = i + 1)
    {
        int countFreq = 1;
        for (int j = 0; j < n; j = j + 1)
        {
            if (X[j] == X[i])
                countFreq = countFreq + 1;
        }
        if (maxFreq < countFreq)
        {
            maxFreq = countFreq;
            mostFrequent = X[i];
        }
        else if (maxFreq == countFreq)
            mostFrequent = min(mostFrequent, X[i]);
    }
    return mostFrequent;
}

Solution code Python

def mostFrequentElement(X, n):
    maxFreq = 0
    mostFrequent = -1
    for i in range(n):
        countFreq = 1
        for j in range(n):
            if X[j] == X[i]:
                countFreq = countFreq + 1
        if maxFreq < countFreq:
            maxFreq = countFreq
            mostFrequent = X[i]
        elif maxFreq == countFreq:
            mostFrequent = min(mostFrequent, X[i])
    return mostFrequent

Time and space complexity analysis

We are running a nested loop and performing an O(1) operation at each iteration. The time complexity is n*n*O(1) = O(n^2). We are using a constant number of extra variables, so the space complexity is O(1).

Using sorting and a single scan

Solution Idea

Now, the critical question is: how can we improve the time complexity? Searching is an essential operation in the problem. Can we think of a way to improve the time complexity of searching?

If we sort the array, then all duplicate elements will get placed adjacent to each other. We can easily scan the array, count the frequency of each element, and return the element with the max frequency. Compared to the above approach, this ensures that the frequency is calculated only once for each unique element.

Solution steps

Step 1: We first sort the array using some efficient O(nlogn) sorting algorithm like merge sort, heap sort, or quicksort. Let's suppose we are using heap sort, which works efficiently in place.

Step 2: We initialize two variables: maxFreq to track the maximum frequency and mostFrequent to track the most frequent element. maxFreq is initialized to 0, and mostFrequent is initialized to -1.

Step 3: Now we scan the sorted array using a loop until i is less than n. Inside the loop, we initialize the variable countFreq to track the frequency count of each element. We set countFreq to 1.

• We start from the first element (i = 0) and search for its consecutive occurrences using a while loop until X[i] is not equal to X[i + 1]. In other words, this inner while loop will end when X[i] != X[i + 1], and in such a situation, we have moved to the next unique element in the sorted array. During this process, we increase countFreq and i by 1.
• After the inner while loop, if (maxFreq < countFreq), we found an element X[i] with a frequency greater than the maximum frequency count till that point. So we update maxFreq with countFreq and mostFrequent with X[i]. If (countFreq == maxFreq), we also update the mostFrequent with the minimum of mostFrequent and X[i].
• Now we go to the next iteration of the outer loop and repeat the same process for the next unique element available at index i.

Step 4: By the end of the outer loop, we return the value stored in mostFrequent.

Solution code C++

int mostFrequentElement(int X[], int n)
{
    sort(X, X + n);
    int maxFreq = 0;
    int mostFrequent = -1;
    int i = 0;
    while (i < n)
    {
        int countFreq = 1;
        while (i + 1 < n && X[i] == X[i + 1])
        {
            countFreq = countFreq + 1;
            i = i + 1;
        }
        if (maxFreq < countFreq)
        {
            maxFreq = countFreq;
            mostFrequent = X[i];
        }
        else if (maxFreq == countFreq)
            mostFrequent = min(mostFrequent, X[i]);
        i = i + 1;
    }
    return mostFrequent;
}

Solution code Python

def mostFrequentElement(X, n):
    X.sort()
    maxFreq = 0
    mostFrequent = -1
    i = 0
    while i < n:
        countFreq = 1
        while i + 1 < n and X[i] == X[i + 1]:
            countFreq = countFreq + 1
            i = i + 1
        if maxFreq < countFreq:
            maxFreq = countFreq
            mostFrequent = X[i]
        elif maxFreq == countFreq:
            mostFrequent = min(mostFrequent, X[i])
        i = i + 1
    return mostFrequent

Time and space complexity analysis

If we observe the nested loop, the outer loop picks the unique elements, and the inner loop counts the frequency of that element. So we are accessing each element only once and performing an O(1) operation (Think!). The time complexity of the nested loop is n * O(1) = O(n).

The overall time complexity is the time complexity of heap sort plus the time complexity of the nested loop, which is O(nlogn) + O(n) = O(nlogn). The space complexity is O(1) because heap sort works in place, and we are using a constant number of variables.

Using a hash table to store the frequency count

Solution idea and steps

Again, how do we further improve time complexity? Can we use a hash table to perform searching efficiently? A hash table performs basic dictionary operations like insertion, deletion, and searching operations in O(1) average time. So here is another idea:

• We create a hash table H to store elements and their frequency counts as key-value pairs.
• Now we scan the array to check if the value associated with any element exists in the hash table or not. If it exists, we increment the frequency count (value) of the element (key) by 1. If not, we store the frequency count of that element as 1. 
• During iteration, we also store the most frequent element and its frequency count in the variables mostFrequent and maxFreq, respectively. We update the value of these variables if we find the stored frequency count of any element greater than the current maximum frequency count.
• And finally, we return the most frequent element found, i.e., mostFrequent.

Solution pseudocode

int mostFrequentElement(int X[], int n)
{
    HashTable H
    int maxFreq = 1
    int mostFrequent = -1
    for (int i = 0; i < n; i = i + 1)
    {
        if (H.search(X[i]))
        {
            H[X[i]] = H[X[i]] + 1
            if (maxFreq < H[X[i]])
            {
                maxFreq = H[X[i]]
                mostFrequent = X[i]
            }
            else if (maxFreq == H[X[i]])
                mostFrequent = min(mostFrequent, X[i])
        }
        else
            H[X[i]] = 1
    }
    return mostFrequent
}

Solution code C++

int mostFrequentElement(int X[], int n)
{
    unordered_map<int, int> H;
    int maxFreq = 1;
    int mostFrequent = -1;
    for (int i = 0; i < n; i = i + 1)
    {
        if (H.find(X[i]) != H.end())
        {
            H[X[i]] = H[X[i]] + 1;
            if (maxFreq < H[X[i]])
            {
                maxFreq = H[X[i]];
                mostFrequent = X[i];
            }
            else if (maxFreq == H[X[i]])
                mostFrequent = min(mostFrequent, X[i]);
        }
        else
            H[X[i]] = 1;
    }
    return mostFrequent;
}

Solution code Python

def mostFrequentElement(X, n):
    H = {}
    maxFreq = 1
    mostFrequent = -1
    for i in range(n):
        if X[i] in H:
            H[X[i]] = H[X[i]] + 1
            if maxFreq < H[X[i]]:
                maxFreq = H[X[i]]
                mostFrequent = X[i]
            elif maxFreq == H[X[i]]:
                mostFrequent = min(mostFrequent, X[i])
        else:
            H[X[i]] = 1
    return mostFrequent

Solution code Java

int mostFrequentElement(int[] X, int n) 
{
    HashMap<Integer, Integer> H = new HashMap<>();
    int maxFreq = 1;
    int mostFrequent = -1;
    for (int i = 0; i < n; i = i + 1) 
    {
        if (H.containsKey(X[i])) 
        {
            H.put(X[i], H.get(X[i]) + 1);
            if (maxFreq < H.get(X[i])) 
            {
                maxFreq = H.get(X[i]);
                mostFrequent = X[i];
            }
            else if (maxFreq == H.get(X[i]))
                mostFrequent = Math.min(mostFrequent, X[i]);
        }
        else
            H.put(X[i], 1);
    }
    return mostFrequent;
}

Time and space complexity analysis

We are doing single scan of array and, at each iteration, performing constant operations. In other words, we are searching for each element once and inserting/updating it once. Time Complexity = n*O(1) = O(n). Space complexity = O(n) for storing elements in hash table.

Critical ideas to think!

• Can we try to solve this problem using BST? If yes, then what would be the time complexity?
• Can we solve this problem using some other approach?
• How can we optimize the brute force approach further? How do we ensure that the frequency is calculated only once for each unique element?
• How can we optimize the 2nd approach further? Would it be possible to use binary search after sorting to find the most frequent element?
• What if all elements were unique? What changes will you make?

Comparisons of time and space complexities

• Using nested loops: Time = O(n^2), Space = O(1)
• Using sorting and linear scan: Time = O(nlogn), Space = O(1)
• Using hash table: Time = O(n), Space = O(n)

Suggested coding problems to practice

• Find the most frequent word in a sentence
• Sort characters by frequency
• Find the frequency of all words in a sentence
• Find the least frequent element in the array
• Find the top k frequent elements in the array
• Find the kth most frequent element in an array
• Find the first non-repeating element in an array
• Find the smallest missing positive integer in an array
• Find the element that appears once in an array where every other element appears twice

If you have any queries/doubts/feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!