Difficulty: Easy, Asked-in: Facebook, Uber
Key takeaway: An excellent-searching problem to learn problem-solving and time complexity optimization using sorting and hash table.
Given an array X[] of size n, write a program to find the most frequent element in the array, i.e. the element which occurs the maximum number of times.
Example 1
Input: X[] = [2, 12, 1, 2, 8, 2, 2, 1, 8, 2], Output: 2
Explanation: 2 is 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[] = [1, 9, 2, 1, 2], Output: 1
Explanation: 1 and 2 are repeated two times, then we return the smallest of them i.e. 1.
The basic idea would be to count occurrences of each element and return element with the maximum number of occurrences. We can use nested loop: pick each element using outer loop and scan entire array to count frequency using inner loop. Here are solutions steps:
We run outer loop from i = 0 to n - 1 and inner loop from j = 0 to n - 1 to count frequency. Before starting inner loop, we also initialize a variable countFreq to track the frequency count of each element i.e. countFreq = 1.
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
}
We are running nested loop and performing O(1) operation at each iteration. Time complexity = n*n*O(1) = O(n^2). We are using constant number of extra variables, space complexity = O(1)
Now critical questions are: How do we improve the time complexity? Searching is an essential operation in the problem. Can we think 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 frequency of each element and return the element with max frequency. Compared with the above approach, this ensures that frequency is calculated only once for each unique element.
Now we scan sorted array using a loop till i < n. Inside loop, we initialize variable countFreq to track the frequency count i.e. countFreq = 1.
int mostFrequentElement(int X[], int n)
{
heapSort(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
}
If we observe nested loop, outer loop pick the unique elements, and inner loop counts the frequency of that element. So we are accessing each element only once and performing O(1) operation (Think!). Time complexity of nested loop = n * O(1) = O(n).
Overall time complexity = Time complexity of heap sort + Time complexity of nested loop = O(nlogn) + O(n) = O(nlogn). Space complexity = O(1), because heap sort works in-place and we are using constant number of variables.
Again, how do we further improve time complexity? Can we use a hash table to perform searching efficiently? Hash table performs basic dictionary operations like insertion, deletion, and searching operation in O(1) average. So here is another idea:
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
}
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.
Enjoy learning, Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.