209. Majority Element II
You are given an integer array nums of length n. Find every value that occurs strictly more than ⌊n/3⌋ times.
A quick counting argument shows at most two such values can exist (three values each above n/3 would need more than n elements in total). Return the qualifying values in increasing order; if nothing crosses the threshold, return an empty list.
The classic follow-up: can you do it in linear time using only constant extra space?
Example 1:
Input: nums = [3, 2, 3]
Output: [3]
Explanation: n = 3, so the threshold is ⌊3/3⌋ = 1. Only 3 appears more than once.
Example 2:
Input: nums = [1, 2]
Output: [1, 2]
Explanation: n = 2, so the threshold is ⌊2/3⌋ = 0, and both values appear more than 0 times.
Constraints:
- 1 ≤ n ≤ 5 * 10⁴
- -10⁹ ≤ nums[i] ≤ 10⁹
Hints:
Counting occurrences with a hash map and keeping every value above ⌊n/3⌋ solves it immediately in O(n) time and O(n) space. The interesting part is shaving the space.
Boyer–Moore voting generalizes: since at most two values can each exceed n/3, track two candidates with two counters. When an element matches a candidate, bump that counter; when a counter is 0, adopt the element; otherwise decrement both.
Voting only tells you who *survived*, not who actually won — finish with a second pass that recounts the two candidates and keeps only those genuinely above ⌊n/3⌋.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, 2, 3]
Expected output: [3]