Find Boyer-Moore Majority Vote in Java

Title: Find Boyer-Moore Majority Vote in Java

In this guide, you will learn how to find the majority element of an array using the Boyer-Moore Majority Vote algorithm in Java. A majority element is one that appears more than n/2 times, where n is the length of the array, and Boyer-Moore solves the problem in linear time while using only two integer variables of extra memory.

Let’s explore why this classic voting algorithm is such a favorite in coding interviews, walk through a complete Java program, trace it on a concrete input, and finish with the follow-up questions an interviewer is most likely to ask after you solve the base problem.

Understanding the Problem

You are given an integer array nums. Return the element that appears strictly more than nums.length / 2 times. If no such element exists, the algorithm should report that fact clearly rather than return a misleading value.

A naive approach would sort the array and return nums[n / 2] in O(n log n) time, or count every element in a HashMap in O(n) time with O(n) extra space. The Boyer-Moore Majority Vote algorithm improves on both: it runs in O(n) time and uses O(1) extra memory. The intuition is that if a majority element truly exists, then pairing it off against every non-majority element still leaves at least one copy of the majority element standing at the end.

Approach / Algorithm Steps

The algorithm runs in two passes. The first pass picks a candidate; the second pass verifies it.

1. Validate the input. If the array is null or empty, throw an IllegalArgumentException.
2. Initialize candidate to any value and count to 0. These are the only two variables the first pass needs.
3. Iterate over every element num in the array. If count is 0, set candidate to num and reset count to 1.
4. Otherwise, if num equals candidate, increment count. If it does not, decrement count.
5. After the first pass, candidate holds the only element that could possibly be the majority. It is not yet confirmed.
6. Run a second pass that counts how many times candidate actually appears.
7. If that count is strictly greater than nums.length / 2, return candidate. Otherwise, no majority element exists; throw an IllegalStateException.

Java Program

The following program implements the full two-pass algorithm with input validation and a sample main method you can run as-is.

public class BoyerMooreMajorityVote {
    public static int findMajority(int[] nums) {
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("Array must be non-empty");
        }
        int candidate = nums[0];
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
                count = 1;
            } else if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
        int occurrences = 0;
        for (int num : nums) {
            if (num == candidate) {
                occurrences++;
            }
        }
        if (occurrences > nums.length / 2) {
            return candidate;
        }
        throw new IllegalStateException("No majority element exists");
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        System.out.println("Majority element: " + findMajority(nums));
    }
}

Explanation of the Program

The method findMajority accepts an int[] and returns the majority element. The first if block rejects a null or empty array because the concept of a majority is not defined there, and silently returning 0 or -1 would mask bugs in callers.

The first pass is the voting phase. Each iteration either consumes a vote for the current candidate (incrementing count), cancels a vote (decrementing count), or installs a fresh candidate when count drops to 0. The key insight is that every decrement pairs a majority element with a non-majority one, and because the majority element appears more than n/2 times, there is always at least one left unpaired.

The second pass is the verification phase. Boyer-Moore guarantees that if a majority element exists, candidate holds it after the first pass, but it does not guarantee that a majority element exists at all. On an input like {1, 2, 3}, the algorithm would still produce some candidate, so you must count its occurrences and compare against nums.length / 2 before trusting the result.

Step-by-Step Trace

Let’s dry-run the first (voting) pass on the input [1, 3, 1, 3, 1, 2, 1]. The expected majority is 1, which appears 4 times out of 7.

At the end of each iteration, candidate holds the only value for which the running count of matches minus mismatches in nums[0..i] is non-negative. The second pass then confirms that 1 occurs 4 times, which is strictly greater than 7 / 2 = 3, so the method returns 1.

Examples

Example 1: A clear majority

The element 2 appears 4 times in a length-7 array, so it is the majority.

int[] nums = {2, 2, 1, 1, 1, 2, 2};
int majority = findMajority(nums);
System.out.println(majority);
// Output: 2

Example 2: Majority wins despite scattered noise

Even when the majority element is not consecutive, the voting pass still identifies it correctly.

int[] nums = {5, 1, 5, 2, 5, 3, 5, 5, 5};
int majority = findMajority(nums);
System.out.println(majority);
// Output: 5

Example 3: No majority exists

When no element appears more than n/2 times, the verification pass fails and the method throws an exception.

int[] nums = {1, 2, 3, 4};
try {
    findMajority(nums);
} catch (IllegalStateException e) {
    System.out.println(e.getMessage());
}
// Output: No majority element exists

Common Mistakes to Avoid

These are the mistakes that cost candidates points on Boyer-Moore in interviews. Each one has a quick, concrete fix.

• Skipping the verification pass – on an input with no majority like {1, 2, 3}, the voting pass still returns some candidate (3 in this case), and callers silently receive a wrong answer. Always run the second pass unless the problem statement guarantees a majority exists.
• Using >= instead of > in the verification – on {1, 1, 2, 2} an element appearing exactly n/2 times would be wrongly reported as the majority. The definition requires strictly more than n/2, so compare with >.
• Resetting count to 0 instead of 1 when installing a new candidate – the current element is itself a vote for the new candidate, so count must become 1. Setting it to 0 drops that vote and corrupts every later comparison.
• Using equals instead of == for an int[] – works for boxed Integer arrays by accident, but not for primitive int. For Integer[] you must use equals because == compares references and fails outside the integer cache range.
• Returning the wrong sentinel on no majority – returning -1 or Integer.MIN_VALUE hides the problem from callers, who may silently use the fake value. Throw an exception or return an OptionalInt so the absence is explicit.

Edge Cases to Test

Walk the interviewer through this checklist before you declare the solution complete. The first three are the ones a strong candidate names unprompted.

• Empty array
• Null array reference
• Single-element array
• No majority element
• All identical elements
• Majority element is Integer.MIN_VALUE or Integer.MAX_VALUE
• Majority appears exactly n/2 + 1 times (the minimum qualifying count)
• Array of length 2 with two different elements

Additional Considerations

The time complexity is O(n): each pass visits every element exactly once, so the total work is linear in the input size. The space complexity is O(1), since the algorithm uses only a fixed number of integer variables regardless of input size. That constant-memory property is what makes Boyer-Moore stand out against hash-map or sorting-based approaches.

A subtle trade-off is that the algorithm destroys information along the way: after the first pass, you know the candidate but have lost all evidence of which other elements were close contenders. If the problem later asks for the second most frequent element, you cannot recover it from the first pass and must switch to a different approach, usually a HashMap or a bucket-sort of frequencies.

When the input contains boundary values like Integer.MIN_VALUE, the algorithm still works correctly because it only compares elements for equality; there is no arithmetic on the array values that could overflow. The only arithmetic happens on count, which never exceeds nums.length.

Interview Follow-up Questions

These are the variants an interviewer is likely to ask after you solve the base problem. Each hint names an approach, not the full solution.

• What if the problem guarantees that a majority element always exists? – skip the verification pass entirely; the voting pass alone is enough, cutting the work by half.
• What if you must find every element appearing more than n/3 times? – generalize Boyer-Moore to track two candidates and two counts; at most two such elements can exist, and verification still runs in a single pass.
• What if the input arrives as a stream and you cannot store it? – the first pass is already streaming-friendly, but the verification pass needs a second read of the stream or an a priori guarantee that a majority exists.
• What if the array is read-only and distributed across many machines? – run Boyer-Moore locally on each shard to get a local candidate and count, then combine shard results pairwise using the same voting rule; the final candidate is the global majority if one exists.
• How would you adapt the algorithm to find the mode of a sorted array in O(1) space? – a single linear pass tracking the current run length and the best run length suffices when the input is sorted, which is simpler than Boyer-Moore but requires the ordering guarantee.

Conclusion

Boyer-Moore Majority Vote is a textbook example of how a clever invariant can beat a general-purpose data structure. By pairing differing votes against each other during a single linear scan, it compresses what looks like a counting problem into two integer variables, and the verification pass turns a probabilistic-feeling trick into a provably correct algorithm.

Try adapting the code to return an OptionalInt, to handle an Integer[] with proper equals comparisons, or to generalize to the n/3 variant with two candidates. You can learn more about array algorithms here: Arrays.