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 the occurrences of each element and return the element with the maximum number of occurrences. We can use two nested loops: pick each element using the outer loop and scan the entire array to count the frequency using the inner loop. Here are solutions steps:
We run an outer loop from i = 0 to n-1 and an inner loop from j = 0 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.
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 two nested loops and performing an O(1) operation at each iteration. So time complexity = n*n*O(1) = O(n^2). We are using a constant number of extra variables, so space Complexity = O(1)
Now the critical question is: how do we improve the time complexity? Searching is the essential operation in the problem, so can we improve the time complexity of the searching? Let's think!
If we sort the array, then all the 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 max frequency. Compared with the above approach, this ensures that frequency is calculated only once for each unique element.
Now we scan the sorted array using a loop till i < n. Inside the loop, we initialize a 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 the nested loops, outer loops pick the unique elements, and the inner loop counts the frequency of that element. So we are accessing each element only once and performing O(1) operation (Think!). So the time complexity of the nested loops = n*O(1) = O(n).
Overall Time complexity = Time complexity of the heap sort + Time complexity of the nested loops = O(nlogn) + O(n) = O(n). Space Complexity = O(n), because heap sort works in-place and we are using some constant number of variables.
Again, how do we further improve the 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 a single scan of the array and, at each iteration, performing constant operations. In other words, we are searching for each element once and inserting/updating it’s once. So, time Complexity = n*O(1) = O(n). Space Complexity = O(n) for storing elements in the Hash Table.
Enjoy learning, Enjoy algorithms!
Given an array A[] of integers, find out the maximum difference between any two elements such that the larger element appears after the smaller element. In other words, we need to find max(A[j] - A[i]), where A[j] > A[i] and j > i. This is an excellent problem to learn problem-solving using divide and conquer, transform and conquer and a single loop.
Given an array X[] with n elements, we need to write a program to find the largest contiguous subarray sum. A subarray of array X[] of length n is a contiguous segment from X[i] through X[j] where 0<= i <= j <= n. Kadane algorithm idea is intuitive, using a single loop and few variables to solve the problem. We can use a similar idea to solve other coding problems.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.