1041. Majority or Nothing
A town holds a vote where each ballot in nums is the id of the candidate the voter picked. A candidate wins outright only if more than half of all ballots, strictly, were cast for them. Anything else goes to a runoff.
Return the id of the candidate who won outright, or null when nobody did. Because the winning share is strictly more than half, at most one candidate can ever qualify, and exactly half is not enough.
Try to finish in O(n) time with O(1) extra space instead of counting every id in a hash map.
Example 1
- Input:
- nums = [4,4,2,4,3,4,4]
- Output:
- 4
- Explanation:
Candidate 4 holds 5 of 7 ballots, which is more than half.
Example 2
- Input:
- nums = [1,2,3,4]
- Output:
- null
- Explanation:
Every candidate has one ballot out of four, so there is no outright winner.
Example 3
- Input:
- nums = [9]
- Output:
- 9
- Explanation:
The only ballot is more than half of one ballot, so 9 wins.
Constraints
1 ≤ nums.length ≤ 105.
-231 ≤ nums[i] ≤ 231 - 1.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)