Majority Voting Algorithm - WRONG?

Question

A majority voting algorithm decides which element of a sequence is in the majority, provided there is such an element. Here is the most frequently-cited link that I found when I was trying to understand it.

http://www.cs.utexas.edu/~moore/best-ideas/mjrty/index.html

Besides, we have here a link that discusses the problem:

How to find the element of an array that is repeated at least N/2 times?

The problem is that the answer marked as correct is WRONG. Note that the question actually allows the input to have exactly N / 2 copies of a single element (not necessarily more than N / 2 as usually assumed in majority element detection algorithms).

I copied the code and tried it with inputs like [1, 2, 3, 2] and [1, 2, 3, 2, 6, 2] (producing results of 3 and 6). This actually applies as well to the algorithm cited above (which returns "No Majority Element!"). The problem is this: Whenever there's an alternation between the majority element and anything else, the last element in the array that's not the majority element is chosen. Please correct my wrong thoughts if any, and tell me about how to avoid it in the implementation.

Answer 1

The algorithm is correct: there is no majority element in your examples. An element is in the majority only if it is more than 50% of the values.

If you wish to detect the case where the most frequent element has a count of N/2, then I don't see any way to do it in one pass and O(1) space. My best attempt is:

• Run the same algorithm as before, but remember the previous candidate as well.
• If you switched at the last element, then the correct answer is either your current or your previous candidate.
• Run another pass, counting the number of each, and compare them.

Answer 2

OK, so I think I now understand what @sverre is getting at. Here's a proof that it works:

• If exactly N/2 elements are the same value (call this value m), N must be even.

• Split these elements into two parts: the first N-1 elements, and the last element. Given that a total of N/2 elements are equal to m, then either:

  1. the last element is not m, in which case N/2 of the first N-1 elements are equal to m, and therefore the first N-1 elements have a strict majority m; or
  2. the last element is m, in which case (N/2)-1 of the first N-1 elements are equal to m, and therefore the first N-1 elements do not have a strict majority.

• In case 1), m is the candidate just before processing the last element (because, at that point, we've just processed N-1 elements, and we know that a strict majority does exist in this case, so that candidate must be the correct answer).

• In case 2), m is the last element itself. (This is the part which was confusing me: in the usual implementation of the algorithm, this would not necessarily become the candidate as it was processed.)

So:

• For a strict majority (> N/2 elements the same), the answer (if it exists) is the final candidate.

• For a non-strict majority (>= N/2 elements the same), the answer (if it exists) is one of:

  1. the final candidate; or
  2. the candidate just before processing the last element; or
  3. the last element.