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

user_8859213 0
Viewed 15621

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.

data-structures algorithm
5 Answers

There is a well-documented algorithm to do this, known as Boyer-Moore's majority vote algorithm.

Initialize an element m and a counter i with i = 0
For each element x of the input sequence:
If i = 0, then assign m = x and i = 1
else if m = x, then assign i = i + 1
else assign i = i − 1
Return m

It's so simple that it's somewhat hard to believe it's correct, IMO. I recommend reading the proof.

user_7044250
Related