Every time I have ever explained the Boyer-Moore majority element algorithm to someone, people have reliably found it very charming. So now I'm going to explain it to you.

The problem is this: we have an array of elements which we are told possesses a majority element. That is, an element which occurs more than half the time. We would like to figure out what that element is.

There's couple obvious solutions, like, build a map of all the counts, then iterate over that map at the end and find the one with the biggest count. Or sort the list. Both these will reliably tell you what the majority element is, but they both use O(n) space (even if we were to sort the list in-place, this doesn't help if the list was originally a stream).

For an array with random access, there's a simple nondeterministic algorithm that runs in O(1) space and expected linear time: pick an element from the array randomly, then check if it appears more than 50% of the time. In expectation, you'll have to do this twice before you find the true element:

while True:
    candidate = xs[random.randint(0, len(xs) - 1)]
    count = 0
    for x in xs:
        if x == candidate:
            count += 1
    if count > len(xs) // 2:
        return candidate

What's more surprising is that there's also a deterministic algorithm that runs in O(1) space and linear time:

• Remember an item and a count, starting with the first element and 1.
• Every time we look at another element, if it matches the one we are remembering, increment the counter. Otherwise, decrement it. If we get negative, swap to the most recent element we've seen.

The item we're remembering when we hit the end of the array is the majority element (assuming one exists! If there isn't one, then the result is meaningless):

def bm(xs):
    item = None
    count = 0
    for x in xs:
        if count == 0:
            item = x
            count = 1
        elif x == item:
            count += 1
        else:
            count -= 1
    return item

I don't think this one is obviously correct. At least, it's not easy for me to convince myself it is. I think a straightforward induction argument doesn't quite work because the existence of the majority element is a global property and doesn't hold for prefixes of the array. You can do some kind of more complex induction (at least, the Wikipedia page has one) but I don't find it all that visceral for aiding my understanding of why this algorithm works.

The best intuition I've come up with is to translate the algorithm state into a graph. Imagine a star graph that extends infinitely in all directions, with one arm for every element. You might say that each element lives at the limit of each arm:

We begin at the very center of this graph, the hub vertex (this is "item = None, count = 0"). And whenever we see an element in our array, we move towards it in the graph. That means that if it matches our current item we increment the count, otherwise we decrement. This corresponds to either moving away from the hub or towards the hub. In this model, the count variable is always our distance from the hub, and the item variable is always whichever arm we're in.

Since there's a majority element, we're guaranteed to move towards one particular arm more times than all the others put together, so at the conclusions of the algorithm, we're guaranteed to be in the arm that corresponds to the majority element.

I was thinking about this algorithm recently because I realized that it generalizes to a not-particularly-good but extremely simple "recent heavy-hitters" algorithm if you exponentially decay they counter. There are like, real ones of these, but not ones that can be implemented so simply if you just need to whip something up. Check this out:

def track(xs, factor=0.9):
    item = None
    count = 0
    for x in xs:
        if count == 0:
            item = x
            count = 1
        elif x == item:
            count = (count * factor) + 1
        else:
            count = max(0, (count * factor) - 1)
        yield item

Do people still care about "you can implement it in a few lines" as a metric? I dunno, but for lines-of-code to working general-idea, you can get something sort of decent:

I don't know what kind of guarantees this algorithm provides or even what guarantees make sense to ask for for such a thing, but it's a fun little trick when you know you might have a single big boy and want a low-friction way of tracking it.