Easy · Boyer-Moore Voting
Understand → Visualise → Practice.
A value appears more than half the time. Return that majority value using constant extra space.
Pair each majority vote with a different value and cancel both. Because the majority has more than half the votes, it is the only value that can survive all cancellations.
Start with no candidate and a count of 0.
If the count is 0, adopt the current value as candidate. Add 1 when the value matches the candidate, subtract 1 otherwise.
The candidate left at the end is the majority value.
O(n) time and O(1) space.
The trick only works because a majority is guaranteed; without that guarantee you must verify the candidate with a second pass.
Read the full guides first: Big-O and Complexity, Arrays and Dynamic Arrays, Prefix Sums and Difference Arrays.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.