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

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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 timesVisualization
[1] [1] Single element always satisfies > n/3 conditionVisualization
[1, 2] [1, 2] n = 2 → ⌊2/3⌋ = 0, both 1 and 2 appear > 0 timesVisualization
[1, 2, 3, 4] [] No element appears more than n/3 = 1 timesVisualization
[1, 1, 1, 3, 3, 2, 2, 2] [1, 2] n = 8 → ⌊8/3⌋ = 2, 1 and 2 both appear 3 timesVisualization
[] [] Empty array has no elements, returns empty listVisualization
[2, 2] [2] n = 2 → ⌊2/3⌋ = 0, 2 appears 2 timesVisualization
[4, 4, 4, 5, 5, 5, 6] [4, 5] n = 7 → ⌊7/3⌋ = 2, 4 and 5 appear 3 timesVisualization

Solution❯

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]

Algorithm Steps❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
TS
#include <stdio.h>

void majorityElements(int arr[], int n) {
    int candidate1 = 0, candidate2 = 1, count1 = 0, count2 = 0;

    for (int i = 0; i < n; i++) {
        if (arr[i] == candidate1) count1++;
        else if (arr[i] == candidate2) count2++;
        else if (count1 == 0) { candidate1 = arr[i]; count1 = 1; }
        else if (count2 == 0) { candidate2 = arr[i]; count2 = 1; }
        else { count1--; count2--; }
    }

    count1 = count2 = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] == candidate1) count1++;
        else if (arr[i] == candidate2) count2++;
    }

    printf("Majority Elements: ");
    if (count1 > n/3) printf("%d ", candidate1);
    if (count2 > n/3 && candidate1 != candidate2) printf("%d ", candidate2);
    printf("\n");
}

int main() {
    int arr[] = {3, 2, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    majorityElements(arr, n);
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)The array is traversed twice: once for candidate selection and once for verification, both in linear time.
Average CaseO(n)Regardless of the input distribution, both candidate identification and validation phases take linear time.
Worst CaseO(n)Even in the worst-case (e.g., all elements are different), both passes still involve scanning the entire array.

Space Complexity❯

O(1)

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


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...