Moore's Voting Algorithm

Finding the Majority Element: Brute Force vs. Moore's Voting Algorithm

The Majority Element problem asks us to find the element that appears more than half the time in a given array. Let's explore two approaches: brute force and Moore's Voting Algorithm, highlighting their trade-offs.

1. Brute Force (O(n^2) Time, O(1) Space)

The brute-force method checks the count of each element by iterating through the array for every element.

Java

public int majorityElementBruteForce(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (nums[i] == nums[j]) {
                count++;
            }
        }
        if (count > n / 2) {
            return nums[i];
        }
    }
    return -1; // No majority element
}

• Advantage: Simple to understand.

• Disadvantage: Inefficient for large datasets.

2. Moore's Voting Algorithm (O(n) Time, O(1) Space)

Moore's Voting Algorithm is a clever approach using a candidate and a counter.

Java

public int majorityElementMoore(int[] nums) {
    int n = nums.length;
    int candidate = nums[0];
    int count = 1;

    for (int i = 1; i < n; i++) {
        if (nums[i] == candidate) {
            count++;
        } else {
            count--;
            if (count == 0) {
                candidate = nums[i];
                count = 1;
            }
        }
    }

    // Verification (Important!)
    int actualCount = 0;
    for (int num : nums) {
        if (num == candidate) {
            actualCount++;
        }
    }

    if (actualCount > n / 2) {
        return candidate;
    } else {
        return -1; // No majority element
    }
}

• Advantage: Highly efficient, linear time complexity.

• Disadvantage: Slightly more complex to understand.

Which Approach to Choose?

Moore's Voting Algorithm is the clear winner for its efficiency. The brute-force method should only be considered for very small datasets. Understanding Moore's Voting Algorithm is crucial for any programmer dealing with array-based problems.