Over a Third of the Vote
MediumArrays & Hashing
Problem
In a committee ballot, votes[i] is the candidate chosen by member i. A candidate earns a seat if they receive more than ⌊n / 3⌋ votes.
Return every candidate that earns a seat, in ascending order. Use O(1) extra space.
Example 1
- Input:
- votes = [3, 1, 3, 2, 3]
- Output:
- [3]
⌊5/3⌋ = 1; only 3 has more than 1 vote.
Example 2
- Input:
- votes = [1, 2, 1, 2, 3, 1, 2]
- Output:
- [1, 2]
⌊7/3⌋ = 2; both 1 and 2 have 3 votes.
Example 3
- Input:
- votes = [5, 6, 7]
- Output:
- []
Constraints
- 1 ≤ n ≤ 5 · 10^4
- -10^9 ≤ votes[i] ≤ 10^9
Hint
Show the first hint
How many different candidates can each hold more than a third of the votes?
Walkthrough
How to approach it
01Clarify before coding
- Is a winner guaranteed? No, the answer may be empty, so candidates must be verified.
- Strictly more than ⌊n/3⌋? Yes; exactly ⌊n/3⌋ votes is not enough.
- Output order? Ascending, so the result is unique.
02Brute force
Count each candidate with a hash map and keep those above the threshold; or sort and measure runs.
Cost: Hash map: O(n) time, O(n) space. Sorting: O(n log n) time.
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.