Linear time majority algorithm?

Question

Can anyone think of a linear time algorithm for determining a majority element in a list of elements? The algorithm should use O(1) space.

If n is the size of the list, a majority element is an element that occurs at least ceil(n / 2) times.

[Input] 1, 2, 1, 1, 3, 2

[Output] 1

[Editor Note] This question has a technical mistake. I preferred to leave it so as not to spoil the wording of the accepted answer, which corrects the mistake and discusses why. Please check the accepted answer.

Answer 1

I would guess that the Boyer-Moore algorithm (as linked to by nunes and described by cldy in other answers) is the intended answer to the question; but the definition of "majority element" in the question is too weak to guarantee that the algorithm will work.

If n is the size of the list. A majority element is an element that occurs at least ceil(n/2) times.

The Boyer-Moore algorithm finds an element with a strict majority, if such an element exists. (If you don't know in advance that you do have such an element, you have to make a second pass through the list to check the result.)

For a strict majority, you need "... strictly more than floor(n/2) times", not "... at least ceil(n/2) times".

In your example, "1" occurs 3 times, and other values occur 3 times:

Example input: 1, 2, 1, 1, 3, 2

Output: 1

but you need 4 elements with the same value for a strict majority.

It does happen to work in this particular case:

Input: 1, 2, 1, 1, 3, 2
Read 1: count == 0, so set candidate to 1, and set count to 1
Read 2: count != 0, element != candidate (1), so decrement count to 0
Read 1: count == 0, so set candidate to 1, and set count to 1
Read 1: count != 0, element == candidate (1), so increment count to 2
Read 3: count != 0, element != candidate (1), so decrement count to 1
Read 2: count != 0, element != candidate (1), so decrement count to 0
Result is current candidate: 1

but look what happens if the final "1" and the "2" at the end are swapped over:

Input: 1, 2, 1, 2, 3, 1
Read 1: count == 0, so set candidate to 1, and set count to 1
Read 2: count != 0, element != candidate (1), so decrement count to 0
Read 1: count == 0, so set candidate to 1, and set count to 1
Read 2: count != 0, element != candidate (1), so decrement count to 0
Read 3: count == 0, so set candidate to 3, and set count to 1
Read 1: count != 0, element != candidate (3), so decrement count to 0
Result is current candidate: 3