Find all numbers that appear more than ⌊n/3⌋ times in an array.
Problem
Given an integer array nums, return all elements that appear more than ⌊n / 3⌋ times, where n is the length of the array.
The result can be returned in any order.
Notes
- There can be at most two such elements.
- Your solution should use better than linear extra space if possible.
Intuition
This is a frequency-detection problem with a stricter threshold than the usual majority element case. The key observation is that at most two values can cross the n/3 threshold.
Input Format
- An integer array
nums. n = nums.length.
Output Format
- Return an array containing every value that appears more than
⌊n / 3⌋times. - Order does not matter.
Constraints
- The answer is guaranteed to contain at most two values.
Example 1
Input
nums = [3,2,3]
Output
[3]
Explanation
3 appears 2 times and ⌊3/3⌋ = 1, so it appears more than n/3 times.
Example 2
Input
nums = [1,1,1,3,3,2,2,2]
Output
[1,2]
Explanation
1 appears 3 times and 2 appears 3 times. Since ⌊8/3⌋ = 2, both qualify.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.