An array contains one element that occurs strictly more than half the time. Find it.
Finding the majority element can be done in O(1) space. All you need is your current guess and a counter.
Process each element one by one:
- If the counter is zero, that means you have no guess: set your guess to be the current element, and set the counter to be one.
- If the current element is equal to the current guess, then increment the counter.
- Otherwise, decrement the counter.
Once the entire array has been processed, whatever value is stored in the “current guess” variable is the final answer.
Why does this work
Think of the current guess and counter as a bucket of elements. The bucket only stores one kind of element (current guess), but can store multiple of them (counter).
Each time you process an element that is different from the current guess, that element gets discarded alongside one element from the bucket (the counter is decremented). Two distinct elements are discarded. This can happen at most N/2 times. However, we know that there exists a majority element – an element that occurs more than N/2 times, and so it cannot be completely discarded. Therefore it must be in the bucket when the algorithm terminates.
def majority_element(elements): guess = None count = 0 for e in elements: if count == 0: guess = e count = 1 elif guess == e: count += 1 else: count -= 1 return guess
Majority Element only works when you know that there exists an element that occurs more than N/2 times. If you don’t know whether or not this is true, then you need to do a second pass to see how often the guess occurs in the array.
If you have K distinct guesses instead of just one, and you decrement all counters by one when you see a different element, then you will end up finding all elements that occur more than N/(k+1) times. This is known as the Heavy Hitters algorithm.
Majority Element is a streaming algorithm – the algorithm can be stopped at any time.
Majority Element is also known as the Boyer–Moore majority vote algorithm.