Majority Element

Problem

An array contains one element that occurs strictly more than half the time. Find it.

Solution

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.

dnow

Code

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

Extensions

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.

References

Majority Element is also known as the Boyer–Moore majority vote algorithm.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s