Write an algorithm to find the most frequently occurred element in the array. Give Time complexity of algorithm

Question

I'm woking on an assignment of 'Algorithm analysis' and i am stuck with this question i have to submit it tomorrow and i need help. Please answer if you can solve this.

Given an array A of n numbers, write an efficient algorithm to find the most frequently occurred element in that array (Mode of that array). Also analyze the time complexity of your algorithm.

Answer 1

Since this is an assignment, I will give you a hint only about upper bounds of complexity and a similar problem.

This problem is a bit more difficult than the Element Distinctness Problem¹. The element distinctness problem is known as cannot be solved better than O(nlogn) worst case. The solutions for element distinctness are:

1. Sort and iterate - O(nlogn)
2. Create a set/histogram of the elements and check uniqeness. This is done using hashtables in O(n) average case and O(n^2) worst case and O(n) extra space.

Think about both approaches and try to think how you can modify them to solve your problem.
Also, the lower bound of element distinctness tells you there won't be any algorithm better than O(nlogn) worst case.

---

(1) Element Distinctness Problem: Are all elements in the array distinct? Or is there any element that also has a duplicate of itself in it?