Find the Majority Element in a Java Array (Boyer-Moore Voting)

How to Find the Majority Element in an Array in Java

The Majority Element problem is one of the most well-known array problems in coding interviews. A majority element is an element that appears more than n/2 times in an array, where n is the size of the array.

Several approaches can solve this problem, including HashMap frequency counting, sorting, and the highly efficient Boyer-Moore Voting Algorithm. Among these, the Boyer-Moore algorithm is considered the optimal solution because it finds the majority element in O(n) time using only O(1) extra space.

In this tutorial, you'll learn all three methods, understand the intuition behind the Boyer-Moore algorithm, and know when a verification step is necessary.

Problem Statement

Given the following array:

int[] numbers = {2, 2, 1, 1, 1, 2, 2};

Find the element that appears more than n/2 times.

Here,

n = 7

An element must appear at least:

4 times

Output

Majority Element = 2

Method 1: HashMap Frequency Counting

A straightforward solution is to count the frequency of every element using a HashMap.

Example

import java.util.HashMap;
import java.util.Map;

public class Main {

    public static int findMajority(int[] arr) {

        Map<Integer, Integer> frequency = new HashMap<>();

        for (int num : arr) {

            frequency.put(num, frequency.getOrDefault(num, 0) + 1);

            if (frequency.get(num) > arr.length / 2) {
                return num;
            }
        }

        return -1;
    }

    public static void main(String[] args) {

        int[] numbers = {2, 2, 1, 1, 1, 2, 2};

        System.out.println(findMajority(numbers));
    }
}

Output

2

Explanation

Each element's frequency is stored in the map.

As soon as one element appears more than n/2 times, it is returned.

Time Complexity: O(n)

Space Complexity: O(n)

Method 2: Sorting-Based Approach

Sorting the array provides another simple solution.

Example

import java.util.Arrays;

public class Main {

    public static int findMajority(int[] arr) {

        int[] sorted = arr.clone();

        Arrays.sort(sorted);

        return sorted[sorted.length / 2];
    }

    public static void main(String[] args) {

        int[] numbers = {2, 2, 1, 1, 1, 2, 2};

        System.out.println(findMajority(numbers));
    }
}

Output

2

Explanation

If a majority element exists, it must occupy the middle position after sorting because it appears more than half the time.

Time Complexity: O(n log n)

Space Complexity: O(1) (excluding sorting implementation and cloning)

Method 3: Boyer-Moore Voting Algorithm (Optimal)

The Boyer-Moore Voting Algorithm is the most efficient solution.

Example

public class Main {

    public static int findMajority(int[] arr) {

        int candidate = arr[0];
        int count = 1;

        for (int i = 1; i < arr.length; i++) {

            if (count == 0) {

                candidate = arr[i];
                count = 1;

            } else if (arr[i] == candidate) {

                count++;

            } else {

                count--;
            }
        }

        return candidate;
    }

    public static void main(String[] args) {

        int[] numbers = {2, 2, 1, 1, 1, 2, 2};

        System.out.println(findMajority(numbers));
    }
}

Output

2

Explanation

The algorithm maintains:

• A candidate
• A count

Matching values increase the count.

Different values decrease it.

Whenever the count reaches zero, a new candidate is selected.

Time Complexity: O(n)

Space Complexity: O(1)

This is the optimal solution.

Why the Boyer-Moore Voting Algorithm Works

Imagine every occurrence of the majority element canceling out one occurrence of a different element.

Since the majority element appears more than n/2 times, it can never be completely canceled.

Eventually, it becomes the final remaining candidate.

This idea of pairwise cancellation is the key insight behind the algorithm.

Verification Step

The Boyer-Moore algorithm assumes a majority element exists.

If that assumption is not guaranteed, verify the candidate with another traversal.

Example

public class Main {

    public static int findMajorityVerified(int[] arr) {

        int candidate = findMajority(arr);

        int count = 0;

        for (int num : arr) {

            if (num == candidate) {
                count++;
            }
        }

        if (count > arr.length / 2) {
            return candidate;
        }

        return -1;
    }

    public static int findMajority(int[] arr) {

        int candidate = arr[0];
        int count = 1;

        for (int i = 1; i < arr.length; i++) {

            if (count == 0) {

                candidate = arr[i];
                count = 1;

            } else if (arr[i] == candidate) {

                count++;

            } else {

                count--;
            }
        }

        return candidate;
    }
}

The second traversal confirms that the candidate truly appears more than n/2 times.

Step-by-Step Explanation

Consider:

[2, 2, 1, 1, 1, 2, 2]

Initial values:

Candidate = 2

Count = 1

Step 1

Current element:

2

Matches candidate.

Count = 2

Step 2

Current element:

1

Different from candidate.

Count = 1

Step 3

Next element:

1

Different again.

Count = 0

A new candidate will be selected.

Step 4

Current element:

1

New candidate:

Candidate = 1

Count = 1

Step 5

Next element:

2

Different.

Count = 0

Step 6

Last element:

2

New candidate:

Candidate = 2

Count = 1

Final candidate:

2

Internal Working

Throughout the entire algorithm, only two variables are maintained:

Candidate

Count

No additional array or map is required.

This constant memory usage gives the Boyer-Moore algorithm its O(1) space complexity.

Real-Life Analogy

Imagine a room filled with people wearing either red or blue shirts.

Whenever two people wearing different colors meet, they both leave the room.

Because one color represents more than half of the people, it can never be completely eliminated.

Eventually, only the majority color remains.

This is exactly how the Boyer-Moore algorithm works.

Best Practices

• Use the Boyer-Moore Voting Algorithm whenever a majority element may exist.
• Perform the verification step if the existence of a majority element is uncertain.
• Use the sorting approach when the array must already be sorted for another purpose.
• Use the HashMap solution when frequency counts are needed for additional processing.
• Test edge cases such as a single-element array.

Common Mistakes

1. Skipping Verification

Without verification, Boyer-Moore may return an incorrect candidate if no majority element exists.

2. Resetting the Candidate Incorrectly

A new candidate should only be selected when the count becomes zero.

3. Applying the Algorithm to the n/3 Problem

The standard Boyer-Moore algorithm only works for elements appearing more than n/2 times.

Finding elements occurring more than n/3 times requires a modified version.

4. Ignoring Single-Element Arrays

A single-element array always has that element as its majority.

Expert Tips

• Understanding the cancellation principle is more important than memorizing the code.
• The Boyer-Moore algorithm is one of the most elegant examples of reducing space complexity from O(n) to O(1).
• If interviewers ask for indexes or frequencies, the HashMap approach may be more appropriate.
• The Boyer-Moore algorithm can be generalized to solve problems involving elements appearing more than n/k times.

Comparison Table

*Excluding the sorting algorithm's implementation and array cloning.

Frequently Asked Questions

1. What is the Boyer-Moore Voting Algorithm?

It is an algorithm that finds a majority element in O(n) time and O(1) space by repeatedly canceling out different elements until only one candidate remains.

2. Does Boyer-Moore always return the correct answer?

Only if a majority element is guaranteed to exist.

Otherwise, perform a verification pass.

3. What is the time complexity of the Boyer-Moore algorithm?

It runs in O(n) time using O(1) extra space.

4. Can this algorithm find elements appearing more than n/3 times?

No.

That problem requires an extended version of the Boyer-Moore algorithm that tracks multiple candidates.

5. Why does the middle element work after sorting?

A majority element occupies more than half of the array.

After sorting, it must therefore appear at the middle index.

6. What happens if no majority element exists?

The Boyer-Moore algorithm still produces a candidate.

The verification step confirms whether that candidate is actually a majority element.

7. Is the Boyer-Moore algorithm difficult to implement?

The implementation is short.

The real challenge is understanding why the cancellation process always leaves the true majority element as the final candidate.

8. How is the majority element different from the mode?

A majority element appears more than n/2 times.

The mode is simply the most frequently occurring element and may appear much less than half the time