Problem statement

Given a series of data representing the candidates that is voted. Find the candidate with majority votes. Majority means more than 50%. The data could be stream data.

An inuative appraoach is to count and record the number of candidates and once any candidate exceed 50% of total votes, that’s the majority candidate. This approach could be done in linear time, but need O(k) space, where k is number of candidates.

Another simpler approach that solves this problem is invented by Boyer and Moore and called Boyer-Moore majority vote algorithm. The basic principle behand this algorithm is: if there exists a candiate has votes more than half, then this candidate’s vote is more than all other candidates’ votes. Mathematically,

This equation telles us that if we assume a majority, we could use a counter to verify whether this is a true majority by performing:

    for (int num : nums) {
        if (num == majority) counter++;
        else counter--;
    }

If the counter is more than 0, that means it is a majority, else it is not. Following this rule, when the counter is 0, we haven’t found majority, and we could assume the current number is majority, and go to verify it afterwards. If the majority exists afterward, it’s vote should still more than half of the remain votes.

    int counter = 0;
    int majority = -1;

    for (int num : nums) {
        if (majority == num) counter++;
        else if (counter == 0) {
            counter++;
            majority = num;
        } else {
            counter--;
        }
    }

• LeetCode - 169

Use the alroghrim above directly.

• Leetcode - 229

Set two counters, one for the first and another for the second. If any counter becomes 0, we reset the corresponding candidate to the current vote. If we see the same candidate, increases the current counter. Note that only if the vote doesn’t match any candidate, reduce both the counters.

    public List<Integer> majorityElement(int[] nums) {
 
        int m1 = -1, m2 = -1;
        int count1 = 0, count2 = 0;
        
        for (int num : nums) {
            if (m1 == num) {
                count1++;
            } else if (m2 == num) {
                count2++;
            }else if (count1 == 0){
                m1 = num;
                count1++;
            } else if (count2 == 0) {
                m2 = num;
                count2++;
            }  else {
                //only if num doesn't match any candidate, reduce both the counter.
                count1--;
                count2--;
            }

        }
        
        List<Integer> res = new LinkedList<>();
        
        count1 = 0;
        count2 = 0;
        
        // verify 
        for (int num : nums) {
            if (num == m1) count1++;
            else if (num == m2) count2++;
        }
        
        if (count1 > nums.length/3) res.add(m1);
        if (count2 > nums.length/3) res.add(m2);
        
        return res;
    }