[Note] Boyer-Moore Majority Voting

Boyer-Moore Majority Voting

The Boyer-Moore majority voting algorithm is a well-known algorithm used to find the majority element in an array. The majority element is defined as the element that appears more than n/2 times in the array, where n is the size of the array. This algorithm can also be adapted to find elements that appear more than n/k times for any integer k.

Question

You may see some questions asking for counting the vote of someone is over than 1/2 or 1/3. The intuition solution is counting the votes for everyone. However, the space complexity will be O(N). Is there have any solution only use the O(1) for space complexity? It will be the Boyer-Moore majority voting algorithms.

Basic Idea

If we know there is at least one person who gets the 1/2, 1/3, or 1/n votes, we can remove n different votes, and it will not affect the result.

For example, we have three candidates (A, B, C), and A is the candidate who gets at least 1/2 vote. So, we can remove 2 different votes from different candidates, and it will not affect the A has at least 1/n votes.

  • Remove (B, C): It will not affect that A is over 1/2. It will let A's percentage grow up.
  • Remove (A, B): Remove one of the most one and one of the other. It will not affect the truth A is more than 1/2.
  • Remove (A, C): Remove one of the most one and one of the other. It will not affect the truth A is more than 1/2.

As the metioned above, when using Boyer-Moore majority voting algorithms, we need to find the n of different and remove or ignore them. For storing the n votes only spends O(1) space.

The following code finds the votes are more than the floor(n/3) candidate. Also the question from Leetcode 229. Majority Element II.

Code

vector<int> majorityElement(vector<int> &nums) {
    int x = 0, y = 0, cX = 0, cY = 0;

    for (const auto & n: nums) {
        if (n == x)
            cX++;
        else if (n == y)
            cY++;
        else if (cX == 0) {
            x = n;
            cX = 1;
        } else if (cY == 0) {
            y = n;
            cY = 1;
        } else {
            cX--;
            cY--;
        }
    }

    cX = 0;
    cY = 0;
    for (const auto & n: nums) {  
        if (n == x) 
            cX++;
        else if (n == y) 
            cY++;
    }

    vector<int> res;
    if (cX > nums.size() / 3) 
        res.push_back(x);
    if (cY > nums.size() / 3) 
        res.push_back(y);
    return res;
}
Algorithms