**Difficulty:** Easy, **Asked-in:** Facebook, Uber.

**Key takeaway:** An excellent 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 that occurs the maximum number of times.

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

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.

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

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

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

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

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

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

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

**Step 2:** We run the outer loop from **i = 0 to n - 1** and the 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.

- Inside the inner loop, when
**X[i] = X[j]**, we increment countFreq by 1 and move to the next iteration. - 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]. Otherwise, If**countFreq == maxFreq**, we update mostFrequent with the minimum of mostFrequent and X[i], i.e.**min(mostFrequent, X[i])**. - Now we move to the next iteration of the outer loop.

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

```
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;
}
```

```
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
```

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

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.

**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.

**Step 3:** Now we scan the sorted array using a loop until **i < n**. Inside the loop, we initialize the variable **countFreq** to track the frequency count of each element.

- We start from the first element and search for its consecutive occurrences using an inner while loop until
**X[i] != X[i + 1]**. During this process, we increment countFreq and i by 1. - After the inner while loop, if
**maxFreq < countFreq**, we have found an element X[i] with a frequency greater than the maximum frequency count up to that point. So, we update maxFreq with countFreq and mostFrequent with X[i]. Otherwise, if**countFreq == maxFreq**, we update mostFrequent with the**min (mostFrequent , 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.

```
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;
}
```

```
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
```

If we observe the nested while loops, we are incrementing the value of i in each iteration of either the outer loop or the inner loop. So total number of nested loop iterations = n. In other words, we are accessing each element only once and performing O(1) operation. So, the time complexity of nested loop = n * O(1) = O(n).

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

Again, the critical question arises: How can we improve the time complexity? Can we use a hash table to efficiently perform searching? A hash table allows for basic dictionary operations such as insertion, deletion, and searching in O(1) average time. So, here is another idea:

- We create a hash table to store elements and their frequency counts as key-value pairs.
- Now, we scan the array to access each element X[i] and check if the value associated with X[i] exists in the hash table. If it exists, we increment the frequency count (value) of X[i] (key) by 1. If it does not exist, we store the frequency count of X[i] as 1.
- During the iteration, we also keep track of the most frequent element and current maximum frequency count using the variables
**mostFrequent**and**maxFreq**. We update the values of these variables if we find a stored frequency count of any element greater than**maxFreq**. - Finally, we return the value stored in the variable
**mostFrequent**.

```
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;
}
```

```
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
```

```
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;
}
```

We perform a single scan of the array and, at each iteration, carry out constant operations. In other words, we search, insert, or update each element once in the hash table. So time complexity = n * O(1) = O(n). The space complexity = O(n) as we store the elements in the hash table.

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

- 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).

- 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 or feedback, please write us at contact@enjoyalgorithms.com. Enjoy learning, Enjoy algorithms!