Majority Ballot Winner
EasyArrays & Hashing
Problem
A club elects its president by a show of ballots, each ballot holding a candidate number. The rules guarantee that one candidate received more than half of all ballots.
Given the list votes, return that candidate.
Example 1
- Input:
- votes = [3, 1, 3, 3, 2]
- Output:
- 3
3 has 3 of 5 ballots, more than 2.5.
Example 2
- Input:
- votes = [7]
- Output:
- 7
Constraints
- 1 ≤ votes.length ≤ 10^5
- -10^9 ≤ votes[i] ≤ 10^9
- A strict majority candidate always exists.
Hint
Show the first hint
Counting how many ballots each candidate has would answer the question directly.
Walkthrough
How to approach it
01Clarify before coding
- Is a majority guaranteed? Yes, strictly more than half, so the answer always exists and is unique.
- Can there be many distinct candidates? Yes, up to about n / 2 others.
- Is extra memory acceptable? Yes for the main answer; an O(1)-space version is a common follow-up.
02Brute force
For each ballot's candidate, count its occurrences in the whole list and return the first with more than n / 2.
Cost: O(n²) time in the worst case: 10^10 steps for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.