Find Majority Element in Array Using Extended Boyer-Moore Voting Algorithm - Optimal Solution

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.

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]

1. Given an array arr of size n.
2. Initialize two candidates candidate1 and candidate2 and their counts to 0.
3. Traverse the array:
4. → If the current element equals candidate1, increment count1.
5. → Else if it equals candidate2, increment count2.
6. → Else if count1 is 0, set candidate1 to current element and count1 to 1.
7. → Else if count2 is 0, set candidate2 to current element and count2 to 1.
8. → Else decrement both count1 and count2.
9. After the first pass, verify the candidates by counting their actual occurrences in the array.
10. Return the candidates that appear more than n/3 times.

O(1)

Explanation: Only a fixed number of variables are used (two candidates and their counts), independent of the input size.