# Boyer-Moore Voting Algorithm: Find the Majority Element Efficiently

## 👋 Introduction

One of the interesting questions asked in interviews is given an array of size n, find the majority element. The majority element is the one which appears more than **n/2** times in the array.

A brute-force way to solve this problem would count frequencies of each element, but there’s a much smarter way — **the Boyer-Moore Voting Algorithm.**

In this blog, you’ll learn —

* What the problem is?
    
* Why a greedy solution works?
    
* How the Boyer-Moore Voting Algorithm solves it in O(n) time and O(1) space
    
* Java implementation
    
* When and why it works?
    

## 📌 Problem Statement

You are given an array `nums[]`. A **majority element** is one that appears **more than n/2 times** in the array. You need to find that element. You can assume that a majority element **always exists** in the input.

## 🤔 Naïve Approaches

✅ **HashMap Frequency Count – O(n) time, O(n) space**

```java
Map<Integer, Integer> freq = new HashMap<>();
for (int num : nums) {
    freq.put(num, freq.getOrDefault(num, 0) + 1);
    if (freq.get(num) > nums.length / 2) return num;
}
```

While it works, it uses **extra space** to store the HashMap. Can we do better?

## 🧠 Boyer-Moore Voting Algorithm – O(n) Time, O(1) Space

The **Boyer-Moore Voting Algorithm** solves the majority element problem using a clever voting strategy. It doesn’t count frequencies up front — it tracks a **candidate** and a **vote count**.

### ⚙️ How It Works

* Start with no candidate and a vote count of 0.
    
* For each number in the array:
    
    * If the vote is 0, choose the current number as the new candidate.
        
    * If the current number is the same as the candidate, increment the vote.
        
    * Otherwise, decrement the vote.
        

The intuition: Every time you pair off different elements, you reduce the chance for non-majority elements to dominate.

### 🧮 Why It Works

If an element is the **majority**, it will survive all the pairings and remain as the candidate at the end, because it occurs more than the sum of all other elements combined.

## 💻 Java Implementation

```java
public class MajorityElementFinder {

    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }

            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }

    public static void main(String[] args) {
        MajorityElementFinder finder = new MajorityElementFinder();
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        System.out.println("Majority Element: " + finder.majorityElement(nums));
    }
}
```

### 🧪 Output:

```java
Majority Element: 2
```

## ✅ Time and Space Complexity

| Metric | Value |
| --- | --- |

<table><tbody><tr><td colspan="1" rowspan="1"><p>Time Complexity</p></td><td colspan="1" rowspan="1"><p>O(n)</p></td></tr></tbody></table>

<table><tbody><tr><td colspan="1" rowspan="1"><p>Space Complexity</p></td><td colspan="1" rowspan="1"><p>O(1)</p></td></tr></tbody></table>

No extra space is used, and only one pass is needed.

## 🛠️ When to Use It

Use Boyer-Moore when:

* You are guaranteed a majority element (appears &gt; n/2 times)
    
* Only one majority element is present
    
* You need an efficient solution in terms of both time and space
    

## 🔒 Gotchas

If the majority element **might not exist**, you’ll need an extra pass to verify that the candidate actually appears more than n/2 times.

```java
public class MajorityElementFinder {

    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }

            count += (num == candidate) ? 1 : -1;
        }

        // Optional verification if majority element may not exist
        // reset count to 0
        int count = 0;
        for (int num : nums) {
            //count occurences of candidate
            if (num == candidate) count++;
        }
        if (count <= nums.length / 2) throw new IllegalArgumentException("No majority element");
        
        return candidate;
    }

    public static void main(String[] args) {
        MajorityElementFinder finder = new MajorityElementFinder();
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        System.out.println("Majority Element: " + finder.majorityElement(nums));
    }
}
```

## 📚 Summary

The **Boyer-Moore Voting Algorithm** is one of the most elegant greedy algorithms for interview problems. It lets you find the majority element in O(n) time and constant space — a perfect balance of simplicity and power.