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

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

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:

Majority Element: 2

✅ Time and Space Complexity

Time Complexity

O(n)

Space Complexity

O(1)

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

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.