Find Values Occurring More than One Third of the Array
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
Return every value occurring more than floor(n/3) times in nums. Return each qualifying value once; the source prescribes no ordering between qualifying values.
```cpp
vector<int> majorityElement(vector<int>& nums);
```
### Examples
```text
nums = [4,4,2,4,2,2,9] -> [4,2]
nums = [8,9,10] -> []
```
### Constraints
- 1 <= n <= 50000.
- Values lie in [-1000000000,1000000000].
### Follow-up Questions
Can the algorithm use linear time and constant additional space?
### What a Strong Answer Covers
Cancel triples of different values using two candidate slots, then count the surviving candidates in the original array. Explain why every produced result satisfies the source contract and why no required result is omitted.
Overview: Find Values Occurring More than One Third of the Array. Return every value occurring more than floor(n/3) times in nums. Return each qualifying value once; the source prescribes no ordering between qualifying values.
