You are given an integer array nums of length n. Find every element that appears strictly more than ⌊n / 3⌋ times.
Return the qualifying elements in ascending order. If no element clears the bar, return an empty array.
Note the threshold carefully: ⌊n / 3⌋ uses integer division, and the count must be strictly greater. For n = 8 the threshold is 2, so an element needs at least 3 appearances to qualify — and as you'll discover, no more than two elements can ever qualify at once.
n/3 times, their combined count would exceed n — more elements than the array holds. So the answer always has size 0, 1, or 2.[1,2,3] the threshold is ⌊3/3⌋ = 1 and every value appears exactly once, so nothing qualifies — return an empty array.[1,2,3,4]). Recounting the survivors separates real winners from lucky pretenders.k − 1 candidate seats with counters (the Misra–Gries algorithm): a match increments its seat, an empty seat gets claimed, otherwise all k − 1 counters decrement — a k-way cancellation. Verify the survivors with a recount. Time O(n·k) naively or O(n) with a small hash of the candidates, space O(k).⌊n/3⌋ or ⌊2n/3⌋. Check just those two candidates, counting each with binary search over its first and last occurrence — O(log n) total.Input: nums = [3,2,3] Output: [3] n = 3, so the threshold is ⌊3/3⌋ = 1. The value 3 appears 2 times — strictly more than 1.
Input: nums = [1] Output: [1] n = 1, so the threshold is ⌊1/3⌋ = 0. The value 1 appears once — strictly more than 0.
Input: nums = [1,2] Output: [1,2] n = 2, so the threshold is 0. Both values appear once, and 1 > 0 — both qualify.
- 1 <= nums.length <= 5 * 10^4 - -10^9 <= nums[i] <= 10^9
Majority Element asked for one winner past the halfway mark. This sequel lowers the bar to a third — and that small change creates two winners' seats, a possibly empty answer, and one of the most elegant generalizations in algorithm design.
In plain English: tally how many times each value occurs, then report every value whose tally is strictly greater than ⌊n / 3⌋, sorted ascending. The answer holds zero, one, or two values — never three.
Worked example — nums = [1,2,3,1,1,2]
n = 6 → threshold = ⌊6/3⌋ = 2 value count count > 2 ? 1 3 ✓ 2 2 ✗ (needs strictly more than 2) 3 1 ✗ answer: [1]
A few sharp questions before coding show you understand the contract, not just the algorithm.
“Can the array be empty?”
No — the length is at least 1. A single-element array like [1] answers [1], because the threshold ⌊1/3⌋ is 0.
“Can values be negative or very large?”
Yes — values span -10^9 to 10^9, so tally by value with a map or voting scan, never by using values as array indices.
“In what order should the winners be returned?”
Ascending order — sort the result (at most two values) before returning.
“Can the answer be empty?”
Yes — in [1,2,3] every value appears once and the threshold is 1, so nothing qualifies.
“Is the threshold strict?”
Yes — strictly more than ⌊n/3⌋. Appearing exactly ⌊n/3⌋ times does not qualify.
“How large can n get?”
Up to 5 * 10^4 — a nested O(n^2) recount is about 2.5 billion comparisons, far past the time limit. Aim for O(n).
“Is constant extra space expected?”
That is the classic follow-up — yes, an extended Boyer–Moore voting scan achieves linear time with O(1) space.
Before I code, a few quick questions.
The bar is strictly more than the floor of n over 3, so the answer can be empty — correct?
And since three values can never each exceed a third, the answer holds at most two elements.
I will start with a frequency map for correctness, then optimize to constant space with a two-candidate voting scan.
Suppose three values each appeared more than n/3 times. Their combined count would exceed 3 × n/3 = n — more elements than the array holds. Pigeonhole says the answer has size 0, 1, or 2. That single fact shapes the whole solution: we only ever need two candidate seats.
Pick any three mutually different values and delete one copy of each. A true winner loses at most one copy while the array shrinks by three — its share of the array only grows. Repeat until no three distinct values remain: whoever survives is the only possible set of winners.
[1,2,3,1,1,2] --cancel one 1, one 2, one 3--> [1,1,2] 1 held 3 of 6 (half); now 2 of 3 (two thirds) — still over a third
The cancellation scan never eliminates a true winner — but a pretender can luck into a seat. In [1,2,3,4] both seats end occupied, yet nobody appears more than ⌊4/3⌋ = 1 time. Always recount the survivors against the real array before declaring them.
| Brute force | Hash map | Boyer–Moore voting | |
|---|---|---|---|
| Time | O(n²) | O(n) | O(n) |
| Space | O(1) | O(n) | O(1) |
| Idea | Recount every value from scratch | One-pass tally sheet | Two seats, cancel triples, recount |
The full code for each approach lives in the Approaches selector below.
Key takeaway
More than n/k occurrences → at most k − 1 winners → keep k − 1 candidate seats, cancel votes across distinct values, then recount to confirm. For k = 3 that is two seats and two counters: linear time, constant space.
open two seats: (cand1, cnt1) and (cand2, cnt2), counts at 0
for x in nums:
if x matches a live seat → that seat's count += 1
else if some seat's count = 0 → that seat claims x, count = 1
else → both counts -= 1 (triple cancel)
recount cand1 and cand2 in nums; keep those with count > ⌊n/3⌋
return the confirmed winners in ascending order