Boyer-Moore Voting Algorithm for Majority Element

1. The Majority Element Problem

First, let's define the problem. You are given an array of integers nums of size n. The majority element is the element that appears more than n/2 times. Your task is to find this element.

For example:

• In [2, 2, 1, 1, 1, 2, 2], n=7. n/2 = 3.5. The majority element is 2, as it appears 4 times (which is > 3.5).
• In [3, 3, 4], n=3. n/2 = 1.5. The majority element is 3, as it appears 2 times (which is > 1.5).

A key property to note is that if a majority element exists, it is unique. It's impossible for two different elements to both appear more than n/2 times.

2. From Brute-Force to a Better Solution

As is common in technical interviews, let's start by thinking through simpler solutions before arriving at the optimal one.

Approach 1: Brute Force
The most straightforward way is to check every element. For each element in the array, we can iterate through the entire array again to count its occurrences. If any element's count exceeds n/2, we've found our answer.

• Time Complexity: O(n²) — for each of the n elements, we do an O(n) scan.
• Space Complexity: O(1).
  This works, but it's too slow for large inputs and an interviewer will immediately ask you to optimize it.

Approach 2: Using a Hash Map
Since we need to count frequencies, a HashMap is a natural fit. We can iterate through the array once, storing each element and its frequency in the map. As we build the map, we can either check the count after each update or do a second pass over the map to find the element whose count is greater than n/2.

• Time Complexity: O(n) — one pass to populate the map and another to check it.
• Space Complexity: O(k), where k is the number of unique elements. In the worst case (all unique elements), this is O(n).

This is a great improvement and a very respectable solution. However, the follow-up question is almost always: "Can you do it in O(1) space?" This is where the Boyer-Moore algorithm comes in.

The following video provides an excellent summary of these initial approaches before introducing the optimal one.

3. The Optimal Solution: Boyer-Moore Voting Algorithm

This algorithm is a fantastic piece of lateral thinking. It finds the majority element in a single pass with constant extra space. The core intuition is based on a "voting" or "cancellation" process.

Imagine every time you see the majority element, you get one vote. Every time you see a different element, you lose one vote. Since the majority element appears more than n/2 times, it will always have more votes than all other elements combined. Therefore, even after canceling out its votes with every other element, it will still have a positive vote count at the end.

The algorithm works like this:

1. Initialize two variables: candidate (to store the potential majority element) and count (to act as our vote counter), setting count to 0.
2. Iterate through the array one element at a time.
3. For each element:
   • If count is 0, it means we have no active candidate. We select the current element as our new candidate and set its count to 1.
   • If the current element is the same as our candidate, we increment count.
   • If the current element is different from our candidate, we decrement count.

After the loop finishes, the candidate variable will hold the majority element.

Intuition through Cancellation

Let's see why this works. When you encounter a pair of different elements, say (A, B), decrementing the count is like letting them "cancel each other out." Since the majority element M appears more than n/2 times, the number of non-majority elements is less than n/2. In the worst-case scenario, every single non-majority element pairs up with and cancels out an occurrence of M. Even then, M will still have at least one instance left over that was never cancelled. This final, un-cancelled element is our candidate.

The following video gives a superb, detailed explanation of this intuition and a dry run.

4. The Crucial Verification Step

The algorithm as described finds a candidate for the majority element. It correctly finds the majority element if one is guaranteed to exist.

However, as our exercise showed, if there is no majority element, the algorithm will still return whatever element was the candidate at the end. It doesn't guarantee that this candidate is actually the majority element.

Therefore, if the problem statement does not guarantee that a majority element always exists, you must perform a final verification step:

1. After the first pass finds a candidate.
2. Perform a second pass through the array to count the actual occurrences of this candidate.
3. If its count is greater than n/2, return the candidate. Otherwise, there is no majority element.

5. Java Implementation

Now let's put it all together in Java. The following code implements the Boyer-Moore algorithm along with the necessary verification step.

Here is a slightly annotated version of the code for your reference:

import java.util.Arrays;

class Solution {
    public int majorityElement(int[] nums) {
        int n = nums.length;
        int count = 0;
        int candidate = 0; // Can be initialized to any value, will be overwritten.

        // Step 1: Find a candidate for the majority element.
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }

        // Step 2: Verify if the candidate is actually the majority element.
        // This step is only necessary if a majority element is not guaranteed.
        count = 0;
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }

        if (count > n / 2) {
            return candidate;
        }

        // Return a sentinel value if no majority element is found.
        // The problem on platforms like LeetCode often guarantees one exists,
        // so you might not need this part there.
        return -1; 
    }
}

// Driver code
public class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] arr1 = {2, 2, 1, 1, 1, 2, 2};
        System.out.println("Array: " + Arrays.toString(arr1));
        System.out.println("The majority element is: " + sol.majorityElement(arr1)); // Expected: 2

        int[] arr2 = {1, 2, 3};
        System.out.println("\nArray: " + Arrays.toString(arr2));
        System.out.println("The majority element is: " + sol.majorityElement(arr2)); // Expected: -1
    }
}

Complexity Analysis

Let's finalize the analysis for this optimal algorithm.

• Time Complexity: O(n). The algorithm requires at most two passes over the array (one to find the candidate, one to verify). This simplifies to O(n).
• Space Complexity: O(1). We only use a few variables (count, candidate) regardless of the array size. This is the main advantage over the hash map approach.

The Baeldung article "Finding the Majority Element of an Array in Java" (LINK) has a nice summary table comparing all the approaches we've discussed. It's a good final reference.

Conclusion

Congratulations! You've now added another powerful, efficient array algorithm to your toolkit. The Boyer-Moore Voting Algorithm is a perfect interview topic because it tests your ability to grasp a non-trivial concept and understand its edge cases (like the need for verification).

Key Takeaways:

• The Problem: Find the element that appears more than n/2 times.
• The Intuition: Majority elements have more "votes" than all other elements combined, so they will survive a "cancellation" process.
• The Algorithm: A single pass with a candidate and count variable to find a potential majority element.
• The Caveat: A second pass is required to verify the candidate if a majority element is not guaranteed to exist.
• The Performance: O(n) time complexity and O(1) space complexity, making it the optimal solution.

Preview of the next lesson:
We will take a step back from these specialized, clever algorithms and revisit some foundational sorting techniques. In the next lesson, we will implement and analyze bubble sort, selection sort, and insertion sort. While not optimal, understanding these O(n²) sorting algorithms is crucial for building a complete mental model of how sorting works, and they serve as important building blocks for more advanced concepts.