Problem
You are given an array of size n in which one value appears more than n / 2 times. Return that value. Aim for linear time and constant extra space.
Worked examples
Input: nums = [4,4,1,4,2]
Output: 4
4 appears 3 times out of 5, which is more than half.
Input: nums = [6,6,7]
Output: 6
Hints
Hint 1
A hash map of counts works, but can you avoid the extra memory?
Hint 2
If you pair each majority occurrence with a different value and cancel them, something always survives.
Hint 3
Track a single candidate and a counter that goes up on a match and down otherwise.
Solution approach
- Use the Boyer-Moore voting algorithm. Keep a `candidate` and a `count`. When `count` is zero, adopt the current value as the candidate; then increment `count` if the value matches the candidate and decrement it otherwise. Because the majority value outnumbers all other values combined, it cannot be fully cancelled out, so it is the candidate left at the end.
- Dry-run the example, then check boundary cases before explaining time and space costs.
Complexity
O(n) time; O(1) auxiliary space.
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗