Part 2 · Problems · Arrays and hashing
Majority Element
#169 · Easy · LeetCode
Return the element that appears more than n/2 times. It always exists.
[3,2,3] -> 3 [2,2,1,1,1,2,2] -> 2
Ask before coding
- Guaranteed to exist?
Hint
Counting with a Map works. Can you do O(1) memory?
Approach
Boyer-Moore voting: keep a candidate and a vote count. Same value adds a vote, a different one removes a vote. At zero, take the current value as the new candidate. The majority can't be cancelled out.
Time O(n) Space O(1)
Watch it run
Solution (JavaScript, tested)
function majorityElement(nums) {
// Boyer-Moore vote: the majority survives every cancel-out
let candidate = nums[0],
votes = 0;
for (const n of nums) {
if (votes === 0) candidate = n;
votes += n === candidate ? 1 : -1;
}
return candidate;
}Traps
- Only valid because a majority is guaranteed. Otherwise do a second pass to verify.
Say out loud: A map count is the obvious answer. Since a majority is guaranteed, the voting trick gets memory to O(1).