Commissioned for this museum · after Boyer & Moore, 1981
The Majority
TypeScript·1981·23 lines·707 bytes
/**
* Boyer-Moore majority vote — find the value appearing more than half the
* time, in one pass, remembering one candidate and one number.
*/
function majority<T>(items: readonly T[]): T | undefined {
let candidate: T | undefined;
let count = 0;
for (const item of items) {
if (count === 0) {
candidate = item;
}
count += item === candidate ? 1 : -1;
}
// The pass only promises an answer when a majority exists, so the claim
// has to be checked before it is believed.
const seen = items.filter((x) => x === candidate).length;
return seen * 2 > items.length ? candidate : undefined;
}
console.log(majority(["a", "b", "a", "c", "a", "a"]));
console.log(majority(["a", "b", "c"]));Curator’s note
It should not be possible. Finding which value occurs most often ordinarily means counting them all, and counting them all means a table whose size grows with the number of distinct values. This uses one candidate and one integer, looks at each item once, and is right — provided a majority exists.
The way to see it is to stop thinking about counting and think about pairing off. Every time the count returns to zero, the items consumed since it was last zero have cancelled exactly: as many votes against the running candidate as for it. If some value genuinely holds more than half the list, it cannot be cancelled away, because there are not enough other items to pair with it. The survivor at the end is the only thing that could have had a majority — which is a much weaker claim than *does* have one, and the source of every bug people write with this.
Hence the second half of the function, which is not an afterthought and not optional. ["a", "b", "c"] leaves c standing, and c is not a majority of anything. The single-pass part is famous and the verification part is the one that gets dropped, usually by someone who read the clever half on a slide. Honest algorithms come with their preconditions attached.
Boyer and Moore found it in 1981 and did not publish for another decade, by which point it had circulated widely enough that their eventual paper opens by noting the algorithm was already known to people who had never seen it written down. It is the same Boyer and Moore as the string search, who between them have a fair claim to being the most quietly influential pair in the field.