Arrays and Hashing Counting and voting
69. Majority Element II
You are given an array of integers nums of length n. Return every value that appears more than
⌊n / 3⌋ times, in ascending order. If no value appears that often, return an empty list.
⌊n / 3⌋ is n / 3 rounded down, and "more than" is strict. In an array of 9 elements a value needs at
least 4 copies, and in an array of 8 elements at least 3.
Example 1
Input: nums = [4, 1, 4, 7, 1, 4, 1, 9]
[1,4]Explanation: ⌊8 / 3⌋ is 2. The values 1 and 4 appear 3 times each, which is more than 2. The values 7 and 9 appear
once each.
Example 2
Input: nums = [6, -3, 6, 2, 8, -3]
[]Explanation: ⌊6 / 3⌋ is 2. The values 6 and −3 appear exactly twice, which is not more than 2, so no value
qualifies.
Example 3
Input: nums = [5, 9]
[5,9]Explanation: ⌊2 / 3⌋ is 0, so any value that appears at all qualifies. Both values do.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.