Problem
Find every value that appears more than n / 3 times in an array of length n. There can be at most two such values. Aim for linear time and constant space.
Worked examples
Input: nums = [2,1,2,3,1,2,1]
Output: [1,2]
Both 1 and 2 appear 3 times, which exceeds 7 / 3.
Input: nums = [5]
Output: [5]
Hints
Hint 1
Why can there be at most two answers?
Hint 2
Extend the voting idea from the n / 2 version to track two candidates at once.
Hint 3
Candidates from voting are only possibilities; confirm them with a second counting pass.
Solution approach
- Run an extended Boyer-Moore vote with two candidates and two counters. A value matching a candidate bumps that counter; otherwise it fills an empty slot, or if both slots are busy it decrements both counters (cancelling a triple of distinct values). Any value above n / 3 survives this cancellation as a candidate. A second pass counts the two candidates and keeps only those that really exceed n / 3.
- Dry-run the example, then check boundary cases before explaining time and space costs.
Complexity
O(n) time; O(1) auxiliary space.
Report & practice notes
Restated practice version with original examples and explanation. The source is a candidate account, not an official question paper; assessment details can vary. Difficulty is our editorial estimate.
Read the candidate’s source report ↗