The most frequent element in a list (the mode)

I'd be thankful if someone enlighten me how to solve this problem in most efficient manner both in terms of speed and memory consumption.
Example: [4,5,6,7,12,6,8,9,4,6,8,4,97,4] the answer is 4, the only solution that occured to me is to hold counters in a hash table and pick the maximum element. However, there could some circumstances where this could be inefficient, so I wonder if some straightforward method is available.

Thanks beforehand and regards.

The cases when your proposed solution becomes inefficient is when the hash table performance degrades to O(n^2). So, you can design the hash function(s) to avoid this, or you could use a balanced binary tree instead of a hash table, thus accepting slightly slower average case performance as a trade off for better worse case performance.

Alternatively, you could sort the list, and then go through the elements in a single pass to count them. This will result in performance similiar to the use of a balanced binary tree.

Quote:

---

Originally Posted by laserlight

Alternatively, you could sort the list, and then go through the elements in a single pass to count them. This will result in performance similiar to the use of a balanced binary tree.

---

Thanks, I nearly got the idea, however am not sure how to identify the most lengthy subsequence in a sorted list in order to outline the element, could you please explain in detail?

Quote:

---

Originally Posted by AvDav

Thanks, I nearly got the idea, however am not sure how to identify the most lengthy subsequence in a sorted list in order to outline the element, could you please explain in detail?

---

In a sorted list equal elements are grouped next to each other. You search the list once sequencially looking for the largest group of equal elements.