Topic Contents
Problem Statement
Given an integer array arr
, your task is to find all elements that appear more than ⌊n/3⌋
times in the array, where n
is the size of the array.
- You may return the results in any order.
- There can be at most
2
such elements in any array.
If no such element exists, return an empty list.
Examples❯
Input Array | Output | Description |
---|---|---|
[3, 2, 3] | [3] | n = 3 → ⌊3/3⌋ = 1, 3 appears 2 times |
[1] | [1] | Single element always satisfies > n/3 condition |
[1, 2] | [1, 2] | n = 2 → ⌊2/3⌋ = 0, both 1 and 2 appear > 0 times |
[1, 2, 3, 4] | [] | No element appears more than n/3 = 1 times |
[1, 1, 1, 3, 3, 2, 2, 2] | [1, 2] | n = 8 → ⌊8/3⌋ = 2, 1 and 2 both appear 3 times |
[] | [] | Empty array has no elements, returns empty list |
[2, 2] | [2] | n = 2 → ⌊2/3⌋ = 0, 2 appears 2 times |
[4, 4, 4, 5, 5, 5, 6] | [4, 5] | n = 7 → ⌊7/3⌋ = 2, 4 and 5 appear 3 times |
Solution❯
To solve this problem, we need to find elements that appear more than ⌊n/3⌋
times in a given array. The main challenge is to do it efficiently—ideally in linear time and using constant space.
Understanding the Constraint
When we say we want elements that occur more than n/3
times, it means we're looking for items that appear a significant number of times—but not necessarily the most frequent. Because of this threshold, there can be at most two elements that satisfy this condition. Why two? Because if three distinct numbers all appeared more than n/3
times, their total count would exceed n
, which is impossible.
How Do We Approach This?
The trick is to use an extension of the Boyer-Moore Voting Algorithm. The original Boyer-Moore algorithm finds a single majority element (> n/2), but we can extend it to handle two potential candidates:
- We go through the array once, keeping track of two candidates and their counts.
- If we see a number matching a candidate, we increment that candidate’s count.
- If one of the counts is zero, we replace that candidate with the current number and reset the count to 1.
- If the current number matches neither candidate, we decrement both counts.
This gives us up to two potential candidates. But since they are just candidates, we need a second pass through the array to count how many times they actually appear.
Final Validation
Once we've completed the first pass and identified the two candidates, we run a second loop to count how many times each one appears. Only if their count is greater than n/3
, do we include them in the final result.
Case-by-Case Insight
- Single Element: If the array has only one number, that number is the majority by default.
- All Unique Elements: If no number repeats more than ⌊n/3⌋ times, we return an empty list.
- Multiple Valid Candidates: Sometimes two numbers will satisfy the condition—both should be returned.
- Empty Array: There are no elements to count, so the result is an empty list.
This solution is optimal: it runs in O(n) time and uses O(1) space, as we only track two numbers and their counts during traversal.