algorithm - Most common element in an array / Finding the relative majority, deterministically in O(n) time and O(1) space?

Question

So for example, the answer for the array:

1, 11, 3, 95, 23, 8, 1

would be 1, since all the other elements only occur once while 1 occurs twice.

A lot of the questions similar to this question that I've seen on stackoverflow ask to find the absolute majority (the answer occurs at least n/2 in an array of length n), or answer the question using sorting or a hash table. The former is not what I'm asking, and the latter is either too slow ( O(n log n) for sorting ) or uses too much memory ( O(n) for a hash table ).

Does such an algorithm exist? If not, is there a proof showing why it's impossible? Including a source would be nice.

Answer 1

Use the idea from here:

How can we find a repeated number in array in O(n) time and O(1) space complexity

And apply a technique similar to counting sort. That is, create N bins (an array of size N), where N is the largest integer you expect to encounter. This is still O(1) space. Then, iterate through the original array in O(n) time, and when you encounter a value i, increment your results array at index i by 1. Then, iterate through the results array (again O(1) time), finding the largest single value. The index of that value will be the most common value in the original list.