Boyer-Moore Majority Vote

Imagine a room where more than half the people wear red, and everyone else wears some other color. If you keep pairing up one red person with one non-red person and sending both out of the room, red still wins in the end. There were simply more of them to begin with. The Boyer-Moore trick works the same way. It cancels one 'vote' for the current leading candidate against one vote for anything else. Whoever is left standing at the end is the majority.

1. 1Keep a 'candidate' and a 'count', and start count at 0.
2. 2For each item: if count is 0, make this item the new candidate. Then add 1 to count if the item matches the candidate, or subtract 1 if it does not.
3. 3After one full pass, the candidate is the majority item — the value that appears more than half the time. This only works when such a majority actually exists in the list.

Use it to find an item that appears more than half the time in a list, like the winning candidate in an election tally. It does this in a single pass, using almost no extra memory, instead of counting every distinct value with a hash map.

• ⚠Trusting the result without checking that the list actually has a majority item. If no value appears more than half the time, this algorithm still returns some candidate, just not a valid majority.
• ⚠Resetting the candidate on every mismatch, instead of only when count reaches exactly 0. This breaks the cancellation logic.