Maintained by Vikas Dulgunde, software engineer
You are handed a list of numbers. One of those numbers shows up so often that its count alone is greater than half the length of the list. Your job is to report which number that is.
Because it appears strictly more than n/2 times, it is the single most common value by a wide margin, and the problem promises that such a value always exists. You never have to handle the case where no clear winner is present.
The values themselves can be large or negative, and they can be scattered anywhere in the list in any order. The only guarantee you can rely on is the frequency rule: one value crosses the half mark.
The list has length 3, so the winner must appear more than 1.5 times, meaning at least twice. The value 3 appears twice, so it is the answer.
Length is 7, so the winner needs more than 3.5 occurrences, meaning at least 4. The value 2 appears 4 times while 1 appears 3 times, so 2 wins.
Length 3 requires at least 2 copies. The value 5 appears twice, so it is the majority even though it sits at the end.
Visible test cases
Count how many times each value appears, then pick the one whose count passes n/2.
You do not need the full count of every value. You only need to track one running guess and how confident you are in it.
Pair off each occurrence of your current guess against any different value. Since the majority value outnumbers everything else combined, it survives all the cancellations.
Tally every value, then return the first one whose tally exceeds half the array length.
Keep one candidate and a counter. Matching values raise the counter, different values lower it, and a zero counter lets a new candidate take over. The true majority outlasts every cancellation.