Find Majority Element in Array Using Boyer-Moore Voting Algorithm - Visualization

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an array of integers, your task is to find the majority element, which is defined as the element that appears more than ⌊n/2⌋ times in the array (where n is the size of the array).

If a majority element exists, return it. If no such element exists, return -1.

This problem assumes that the array may or may not contain a valid majority element.

Examples❯

Input Array Expected Output Description
[3, 3, 4, 2, 3, 3, 3] 3 3 appears 5 times in an array of size 7 → majority elementVisualization
[1, 2, 3, 4, 5] -1 No element appears more than n/2 = 2.5 timesVisualization
[2, 2, 1, 1, 1, 2, 2] 2 2 appears 4 times → majority in size 7 arrayVisualization
[7] 7 Single element is always the majority (n=1)Visualization
[] -1 Empty array, so no majority elementVisualization
[5, 5, 5, 5, 5, 1, 2] 5 5 appears more than half the timeVisualization
[1, 1, 2, 2, 3, 3] -1 No element appears more than n/2 = 3 timesVisualization

Solution❯

Understanding the Problem

We are given an array of integers, and our goal is to find the majority element—if it exists. But what exactly is a majority element?

A majority element is an element that appears more than n/2 times in the array, where n is the total number of elements. If no such element exists, we return -1.

Approach to Solve the Problem

Step-by-step Explanation Using an Example

Let’s consider the example: [3, 3, 3, 2, 3, 3]

Here, n = 6, so to qualify as a majority, an element must appear more than 6/2 = 3 times, i.e., at least 4 times.

  • Count of 3 = 5 → meets the condition
  • Count of 2 = 1 → does not qualify

So, the answer is 3.

Step-by-step Plan to Solve It

  1. Use the Boyer-Moore Voting Algorithm to identify a candidate.
  2. Verify if the candidate actually occurs more than n/2 times.
  3. If yes, return the candidate; else, return -1.

Intuitive Explanation

Think of it like a voting game. Every time an element agrees with our current "leader", we give it a vote. When it disagrees, we take away a vote. If we run out of votes (count becomes 0), we choose a new leader.

In the end, if there’s a true majority, it will have survived all the challenges and still be the leader.

Edge Cases to Handle

  • Empty Array: No elements → return -1
  • Single Element: [5] → 5 is the majority (only one element)
  • No Majority Element: [1, 2, 3, 4] → all are unique → return -1
  • Tie Situation: [1, 1, 2, 2, 3, 3] → no one has > n/2 count → return -1

Why This Works

Because non-majority elements cancel each other out, only the true majority can remain standing after the count balancing. If no such element exists, the second pass will filter it out.

Algorithm Steps❯

  1. Given an array arr of size n.
  2. Initialize count = 0 and candidate = None.
  3. Traverse the array:
  4. → If count == 0, set candidate = current element.
  5. → If current element == candidate, increment count, else decrement count.
  6. After the loop, candidate is the majority element.
  7. (Optional: Verify candidate by counting its actual occurrences if required.)

Code

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

int majorityElement(int arr[], int n) {
    int count = 0, candidate = 0;
    for (int i = 0; i < n; i++) {
        if (count == 0) {
            candidate = arr[i];
        }
        count += (arr[i] == candidate) ? 1 : -1;
    }
    return candidate;
}

int main() {
    int arr[] = {2, 2, 1, 1, 1, 2, 2};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Majority Element: %d\n", majorityElement(arr, n));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)The algorithm always traverses the entire array once, even if the majority element appears early.
Average CaseO(n)Regardless of element distribution, a single pass over the array is required to maintain count and candidate.
Worst CaseO(n)In the worst case, the candidate may flip multiple times, but the loop still only runs once over the array.

Space Complexity❯

O(1)

Explanation: Only two variables—count and candidate—are used throughout the algorithm, making the space constant.


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...