Return the element that appears more than half the time. It is guaranteed to exist.
DSA Animator › DSA Revision › Arrays › Majority Element
Remember: pair off different values, and the majority survives. Boyer-Moore voting uses one candidate and one counter. The video solves Majority Element (LeetCode 169, Easy) with the Boyer-Moore Voting pattern from the Arrays topic, and you can replay every step in the interactive Majority Element animation.
Return the element that appears more than half the time. It is guaranteed to exist.
For 2, 2, 1, 1, 1, 2, 2, the answer is 2, which appears 4 times out of 7.
Counting with a hash map works, but uses O of n space. Sorting and taking the middle costs O of n log n.
Keep a candidate and a counter. A matching value adds 1, and a different value subtracts 1. When the counter hits 0, the next value becomes the new candidate. The majority outnumbers everything else combined, so it survives.
2 becomes the candidate, and the count is 1. Another 2: the count is 2. Two 1s cancel it down to 0. The next 1 becomes the candidate, with count 1. A 2 cancels it back to 0. The last 2 becomes the candidate, with count 1. The candidate left standing is 2.
In code, if the count is 0, take the current value as the candidate. Then add 1 if the value matches the candidate, or subtract 1 if it does not. Return the candidate, so it's O of n time and O of 1 space.
Remember: pair off different values, and the majority survives. Boyer-Moore voting uses one candidate and one counter.