Boyer-Moore for the curious
You have a good answer already suggesting the use of a Counter. For simplicity,
that's what I would do.
However, I had never heard of the Boyer-Moore algorithm for finding a majority
value in a sequence. Its advantage is that it can achieve O(n) performance
without allocating additional memory to count all of the values, as one does
when using a Counter. To do its bookkeeping, Boyer-Moore needs to hold only an
integer and single value from the sequence. When I read the pseudocode on
it wasn't clear why it worked: the code seemed trivially simple and I could
not immediately see how a few increments and decrements could achieve the
needed goal. Also, the algorithm was interesting because it had an odd
footnote: before returning a candidate value, you have make a final pass over
the sequence actually counting how many times it occurred. It was a
select-and-verify algorithm rather than a just-select-the-right-answer
I wrote a Python implementation and tried to convince myself it works (yes, of
course!) and to get some intuition about how/why. First some terminology:
xs : The input sequence.
x : A value from the sequence.
M : The actual majority value, if any. This is unknown.
m : The currently selected candidate, which might or might not be M.
n : The net-majority status of m since m was selected.
Here's the function I wrote:
# Handle empty input.
if not xs:
# Find a candidate value for the majority (m).
# At any moment, n represents the net-majority status of m.
# A value of zero for n means we have seen non-m values the same
# number of times as m values since m was selected.
n = 0
for x in xs:
if n == 0:
# Net majority status is unclear. Pick a new candidate.
m = x
n = 1
# Otherwise, increment/decrement the net-majority status of m.
n += (1 if x == m else -1)
# Return the candidate only if it is truly the majority.
if xs.count(m) > len(xs) / 2:
And some code to test it:
from collections import Counter
from random import shuffle
# A list with an even number of zeros and ones.
N = 100
ZEROS = [0 for _ in range(N)]
ONES = [1 for _ in range(N)]
EVEN = ZEROS + ONES
# Some test cases using that list.
TESTS = (
(1, EVEN + ),
(1,  + EVEN),
(0,  + EVEN),
(0, EVEN + ),
for exp, xs in TESTS:
got = majority_element(xs)
if got == exp:
print(xs, exp, got, Counter(xs))
if '__name__' == '__main__':
And here is some rough intuition behind its success. In order for a value M to
be the majority value in a sequence, it must be a majority value in at least
one subsection of the sequence. At a very crude level, one can imagine three
flavors of majority-having sequences:
# Front loaded: M sits predominantly toward front of sequence.
1 1 1 1 1 1 0 0 0
# Back loaded: M sits predominantly toward back of sequence.
0 0 0 1 1 1 1 1 1
# Evenly loaded: M is dispersed in a fairly even way across the sequence.
0 1 1 0 1 1 0 1 1
In the front-loaded case,
n will increase and the non-M values at the end of
the list won't be enough to counteract that growth. In the back-loaded case, a
non-M value will be selected as a candidate, but eventually the net-majority
counter will become zero and the algorithm will select an M value. In the
even-loaded case, you can subdivide the sequence into smaller sub-sequences and
the same front-loaded/back-loaded logic can be applied to each sub-sequence.
The algorithm will select the majority within the first sub-sequence and the
remaining sub-sequences (because they are also evenly loaded) won't be able to
counteract that verdict.