Find Majority Element in an Array

Title: Find Majority Element in an Array

Finding the majority element in an array, the value that appears more than half the time, is a classic interview warm-up that opens the door to one of the most elegant algorithms in all of programming: the Boyer-Moore voting algorithm. In this guide, we will explore an efficient Java solution that runs in linear time and uses only a constant amount of extra memory, walk through the voting logic step by step, and then push the problem with a dry run trace, concrete examples, common pitfalls, and interview-style follow-ups.

Understanding the Problem

Given an integer array of length n, we want to return the element that appears strictly more than n / 2 times. By definition, there can be at most one such element because two different values each occupying more than half the array would require more than n slots.

For example, in the array {2, 2, 1, 1, 2, 2, 3} of length 7, the value 2 appears four times. Because 4 > 7 / 2, we return 2 as the majority element. If no element meets that threshold, we signal the error instead of returning a misleading value.

The problem is a good excuse to practice algorithmic thinking under tight memory constraints. A HashMap solves it in O(n) time and O(n) space, but a cleverer approach lets us drop the space usage all the way to O(1) while still running in a single pass.

Approach to Find the Majority Element

The Boyer-Moore voting algorithm scans the array once while maintaining just two variables: a candidate that may be the majority, and a count that measures how strongly the data agrees with that candidate. A second scan then confirms the candidate truly appears more than n / 2 times.

Here are the steps:

1. Guard against a null or empty input by throwing an IllegalArgumentException.
2. Initialize candidate to numbers[0] and count to 1.
3. Scan each subsequent element. If count is 0, adopt the current element as the new candidate and set count to 1.
4. Otherwise, increment count when the element matches candidate; decrement it when the element differs.
5. After the first pass, candidate is the only value that could possibly be the majority element.
6. Run a verification pass that counts how many times candidate actually appears.
7. Return candidate if its occurrences exceed n / 2; otherwise throw an IllegalStateException because no majority exists.

Java Program to Find the Majority Element in an Array

Let us put the approach into a complete, compilable Java program:

public class MajorityElement {

    public static int findMajority(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            throw new IllegalArgumentException("Array must not be null or empty");
        }

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

        // First pass: find a candidate using the Boyer-Moore voting algorithm.
        for (int i = 1; i < numbers.length; i++) {
            if (count == 0) {
                candidate = numbers[i];
                count = 1;
            } else if (numbers[i] == candidate) {
                count++;
            } else {
                count--;
            }
        }

        // Second pass: verify the candidate actually appears more than n/2 times.
        int occurrences = 0;
        for (int value : numbers) {
            if (value == candidate) {
                occurrences++;
            }
        }

        if (occurrences > numbers.length / 2) {
            return candidate;
        }
        throw new IllegalStateException("No majority element exists");
    }

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

Explanation of the Program

• The method findMajority takes an int[] and returns the majority element, or throws an exception if no majority exists.
• The input guard rejects a null reference or an empty array up front so the rest of the method never reads from a non-existent index.
• The variables candidate and count implement the voting logic. Think of count as the net lead of candidate over every other value seen so far: a matching element increases the lead and a differing element cancels one vote on each side.
• When count hits zero, every vote cast so far has been cancelled by an opposing vote, so the current candidate has no claim to the majority of the window up to this index. We replace it with the next element and resume voting.
• The second loop counts the real occurrences of candidate. This check is required because the voting algorithm will always leave some value in candidate, even on inputs that have no majority element at all.
• The main method prints the discovered majority for the sample array {2, 2, 1, 1, 2, 2, 3} so you can run the program and see the algorithm in action immediately.

Step-by-Step Trace

Let us trace the first pass of the voting algorithm on a small input that exercises every branch: matches, mismatches, and the reset when count falls to zero. Consider numbers = {2, 1, 2, 3, 2, 2, 1}; candidate starts at numbers[0] = 2 with count = 1.

At the end of each iteration, candidate is the only value that could possibly be the majority of numbers[0..i]; every other value has already been cancelled out by matching occurrences of candidate. The verification pass that follows confirms whether that single survivor truly appears more than n / 2 times.

Examples

Let us look at a few runs that stress different parts of the algorithm.

Example 1: Clear Majority

int[] arr = {5, 5, 5, 2, 3, 5, 5};
int majority = findMajority(arr);

System.out.println("Majority element: " + majority);
// Output: Majority element: 5

The value 5 appears five times out of seven, well above the n / 2 threshold. The counter stays positive through most of the first pass, which is the easy case for Boyer-Moore.

Example 2: Minimal Majority

int[] arr = {4, 4, 4, 4, 1, 2};
int majority = findMajority(arr);

System.out.println("Majority element: " + majority);
// Output: Majority element: 4

The value 4 appears four times out of six, which is exactly one more than n / 2 = 3. This is the tightest case: any fewer occurrences and 4 would no longer qualify as a majority.

Example 3: No Majority Exists

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

No value appears more than n / 2 = 2 times, so the verification pass fails and the method throws IllegalStateException. This example is why the second pass is not optional, even though the voting pass by itself still produces a plausible-looking candidate.

Common Mistakes to Avoid

Here are the slip-ups learners tend to make when implementing the voting algorithm:

• Skipping the verification pass – the voting loop always leaves some value in candidate, even for inputs like {1, 2, 3, 4} that have no majority at all. Always run the second pass to count the real occurrences and compare against n / 2.
• Using >= instead of > – a majority must appear strictly more than n / 2 times; >= wrongly accepts {1, 1, 2, 2} as having a majority of 1. Use the strict > comparison on the verification count.
• Starting count at zero – initializing count = 0 while leaving candidate = numbers[0] immediately overwrites the candidate on the next element and skews the first several votes. Start with count = 1 so the first element has one vote in its favor.
• Resetting count to zero after a mismatch – some learners replace the count-- step with count = 0 on every mismatch, which discards legitimate votes and returns the wrong value on inputs like {1, 1, 2, 1, 3}. The invariant depends on cancelling exactly one vote at a time.
• Comparing boxed Integer with == – if the input is Integer[] rather than int[], == compares object references and silently misbehaves for values outside the Integer cache range of -128 to 127. Use .equals() or convert to int first.

Edge Cases to Test

Before you declare the implementation done, run it against these boundary inputs:

• Empty array
• Null array reference
• Single-element array
• Two-element array with both elements identical
• Two-element array with the two elements different
• All identical elements
• No majority exists (every value balanced)
• Majority element at exactly n / 2 + 1 occurrences
• Integer.MIN_VALUE or Integer.MAX_VALUE as the majority

Additional Considerations

A few points worth remembering about this algorithm:

1. Time complexity: The first pass visits each of the n elements once in O(n), and the verification pass does the same, so the total running time is O(n).
2. Space complexity: The algorithm uses only two primitive variables, candidate and count, plus the verification counter. The total extra space is O(1) regardless of the array size.
3. Why the voting invariant holds: Every time count is decremented, we pair one vote for candidate with one vote for an opposing value and discard both. A true majority has more votes than every other value combined, so at least one of its votes survives the pairing.
4. Why verification is mandatory: The voting pass guarantees candidate is the only possible majority, not that a majority exists. Without the second count, inputs like {1, 2, 3, 4} would return 4 as a nonexistent majority.
5. Comparison with the HashMap approach: Counting with HashMap<Integer, Integer> also runs in O(n) but allocates an object per distinct key and pays autoboxing on every lookup. Boyer-Moore is faster in practice because it stays entirely in primitives.

Interview Follow-up Questions

Once the base version is working, an interviewer will usually probe deeper with questions like these:

• What if the array is sorted? – if a majority element exists, it must occupy the middle index; return numbers[n / 2] after a single verification pass, giving O(n) time and O(1) space.
• What if you need every element that appears more than n / 3 times? – extend the voting idea to two candidates and two counters; at most two values can appear strictly more than n / 3 times, so one scan plus a verification pass still runs in O(n) with O(1) space.
• What if the input arrives as a stream of unknown length? – run the voting pass as values arrive since it already uses constant memory; the verification pass requires replaying the stream, so you may need to accept the candidate without verification or buffer the data on disk.
• What if the array is distributed across many machines? – compute a (candidate, count) pair per shard, then merge pairs by summing counts when candidates match and subtracting when they differ; this is a parallel form of Boyer-Moore that works because the voting rule is associative.
• Can you return both the majority value and its frequency? – the verification pass already counts the occurrences, so return the pair (candidate, occurrences); the extra information costs no additional work.

Conclusion

In this guide, we walked through finding the majority element in a Java array using the Boyer-Moore voting algorithm. The findMajority method scans the array twice, once to vote on a candidate and once to verify the candidate truly appears more than n / 2 times. The running time is O(n) and the extra space is O(1), which is the best any algorithm can do on this problem.

Try adapting the code to return the frequency along with the majority value, generalize it to find elements that appear more than n / 3 times, or layer it on top of a stream so it handles inputs whose length you do not know in advance. Happy coding!

You can learn more about Array techniques: Arrays