Finding the Majority Element in O(n)

Boyer-Moore Voting Algorithm: Finding the Majority Element

The Boyer-Moore Voting Algorithm is a very efficient way to find the majority element in an array. The majority element is the one that appears more than half the time in the array.

This algorithm works in O(n) time (which means it goes through the array just once) and uses O(1) extra space (which means it doesn’t need much memory).

Let’s break it down step by step:

How it Works:

1. Initialize the Candidate:
   You start with an empty candidate (set to zero) and a counter (set to zero). The candidate will be the potential majority element, and the counter will track how likely it is to be the majority.

2. Iterate through the Array:
   For each element in the array:

   • If the counter is zero, set the current element as the candidate.

   • If the candidate is the same as the current element, increase the counter.

   • If the candidate is different, decrease the counter.

3. Final Candidate:
   After scanning the whole array, the candidate will hold the majority element (if it exists).

Why It Works:

The idea behind the Boyer-Moore algorithm is based on the fact that:

• If there is a majority element, it will always "win" over other elements when you reduce the counter.

• The counter works like a "balance" to cancel out non-majority elements.

• At the end, the candidate is the element that appears more than half the time in the array.

Example:

Let’s look at an example to understand it better.

• Input: [3, 3, 4, 2, 4, 4, 2, 4, 4]

1. Start with candidate = 0, counter = 0.

2. First element is 3. Set candidate to 3, increase counter to 1.

3. Next element is 3. The counter becomes 2.

4. Next element is 4. Decrease counter to 1.

5. Next element is 2. Decrease counter to 0.

6. Now counter is 0, so set candidate to 4, and counter becomes 1.

7. Continue with the next elements, the counter fluctuates, but in the end, the candidate remains 4, which is the majority element.

Output: 4

public class Main {
    public static void main(String[] args) {
        int[] nums = {3, 3, 4, 2, 4, 4, 2, 4, 4};

        int candidate = 0;
        int counter = 0;

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

            if (num == candidate) {
                counter++;
            } else {
                counter--;
            }
        }

        System.out.println("Majority Element: " + candidate);
    }
}

🧾 Output:

Majority Element: 4

Where You Can Use It:

• Finding the Majority Element: If you need to find an element that appears more than half the time in an array, this is perfect.

• Generalized Majority: It can be extended for cases where an element appears more than n/k times (for some k).

• Efficient for Large Datasets: Since the algorithm only needs one pass through the array, it works well for large data or streaming data.

Conclusion:

The Boyer-Moore Voting Algorithm is a clever and efficient solution to finding the majority element in an array. It runs in linear time and uses constant space, which makes it one of the best algorithms for this problem.