Understanding the Problem
We are given an array of integers, and our goal is to find all elements that appear more than ⌊n/3⌋
times. In other words, we want to identify elements that show up frequently—but not necessarily the most frequent one.
This isn’t about just counting and checking frequencies using a hashmap—we want to solve this problem efficiently: in linear time and using constant space.
Step-by-Step Plan with Example
Let’s take the example: [3, 2, 3]
Step 1: What does ⌊n/3⌋ mean?
The length of the array n = 3
. So ⌊n/3⌋ = ⌊1⌋ = 1. That means we want all elements that occur more than once in this array.
Step 2: Why are there at most two valid elements?
Let’s imagine we have three different numbers, and each of them appears more than ⌊n/3⌋ times. That would be more than n
total elements, which is impossible. Hence, we can have at most two elements that satisfy this condition.
Step 3: Using Extended Boyer-Moore Voting Algorithm
This is a clever trick to keep track of up to two candidates:
- We maintain two variables for candidates and their counts.
- If we see the same number again, we increment its count.
- If a count drops to zero, we replace that candidate with the new number.
- If the number doesn’t match either candidate, we decrement both counts.
This way, after the first pass, we end up with at most two candidates who could be the majority elements. But we still need to verify them.
Step 4: Final Verification
Once we have our two candidates, we do a second pass through the array to count their actual occurrences. If either one appears more than ⌊n/3⌋ times, we include it in the final result.
Let’s Solve the Example
Input: [3, 2, 3]
First Pass:
- candidate1 = 3, count1 = 1
- candidate2 = 2, count2 = 1
- next 3: matches candidate1 → count1 becomes 2
Second Pass:
- count of 3 = 2
- count of 2 = 1
Since ⌊3/3⌋ = 1:
→ 3 appears more than once ⇒ include it
→ 2 appears only once ⇒ do not include it
Output: [3]
Edge Cases and How We Handle Them
1. Empty Array
If the array is empty, there are no elements to check. So, we return an empty list.
2. Single Element
If the array has just one element, that element is trivially more than ⌊n/3⌋ times. So we return it.
3. All Unique Elements
Example: [1, 2, 3]
. Here, each element appears once, and ⌊3/3⌋ = 1. So none appear more than that ⇒ return empty list.
4. Two Valid Candidates
Example: [1, 1, 1, 2, 2, 2, 3]
n = 7 → ⌊n/3⌋ = 2
1 appears 3 times → valid
2 appears 3 times → valid
Output: [1, 2]
Comments
Loading comments...