Boyer-Moore’s Majority Voting Algorithm

The algorithm assumes that there is always a majority element in the array.

Moore's Voting Method

The Boyer-Moore voting method is one of the most often used optimum algorithms for determining the majority element among elements with more than N/2 occurrences. This works wonderfully for finding the majority element, which requires two traversals over the provided items and is $O(N)$ time and $O(1)$ space complexity.

Majority Element Problem (leetcode)

class Solution {
public:
 
	int majorityElement(vector<int>& nums) {
	int majorityElement = nums[0];
	int count = 1;
 
	// Voting algorithm
	
	for (int i = 1; i < nums.size(); i++) {
		if (nums[i] == majorityElement) {
			count++;
		} else {
			count--;
			
			if (count == 0) {
				// If count becomes zero, update the majorityElement
				majorityElement = nums[i];
				count = 1;
			}
		}
	}
	
	// At this point, majorityElement should contain the majority element
	return majorityElement;
	}
};

Counting Mechanism

• The algorithm maintains two variables: majorityElement and count
• It iterates through the array and for each element, it either increments the count (if the current element is the same as the assumed majority element) or decrements the count (if the current element is different)
• If the count becomes zero, it means the assumed majority element can be safely replaced with the current element, and the count is reset to 1

Cancellation Effect: The counting mechanism has a “cancellation effect”. When the count becomes zero, it essentially cancels out equal occurrences of the assumed majority element with different elements.

Due to the “cancellation effect”, the majority element (if it exists) will survive till the end. The algorithm guarantees that the final value in the majorityElement variable is indeed the majority element, as it has survived all the cancellations.

To verify that the final result is indeed the majority element, a second pass through the array can be performed to count the occurrences of the final majorityElement. If the count of the final majorityElement is greater than ⌊n / 2⌋, it is confirmed as the majority element.

Overall, the algorithm is an efficient way to find the majority element with a linear time complexity of $O(n)$ and constant space complexity of $O(1)$.