Find All Elements Appearing More Than a Third of the Time
Implement majorityElementII
Given an array
nums, return all elements that appear MORE THAN ⌊n/3⌋ times. It's mathematically impossible for three different values to each exceed a third of the array, so the answer never has more than 2 elements — it may have 0, 1, or 2.
Counting occurrences of every value from scratch works, but it repeats the same scan for every duplicate of a non-qualifying value. The Boyer-Moore votingBoyer-Moore VotingA technique for finding elements that appear more than a fixed fraction of an array by having candidate values "cancel out" against elements that don't match them, using O(1) extra space instead of a frequency map. technique, extended to track two candidates instead of one, finds both possible answers in a single pass — followed by a quick second pass to confirm each one actually clears the bar.
Example 1:
Input: nums = [1,1,1,3,3,2,2,2]
Output: [1,2]
Example 2:
Input: nums = [3,2,3]
Output: [3]
Example 3:
Input: nums = [1,2,3,4]
Output: []
+ 8 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ nums.length ≤ 5×10⁴ - ●
-10⁹ ≤ nums[i] ≤ 10⁹
nums =
[1, 1, 1, 3, 3, 2, 2, 2]