Boyer–Moore Majority Vote

Summary

No one is supposed to invent the Boyer–Moore voting algorithm during the interview. The point is how to write bug-free codes and make interviewers happy. The order of the branches are quite tricky here.

Please remember to increase cnt first, then check if cnt==0, and finally decrease cnt.

Several good points here to mention,

1. There’s only one majority number if it exists;
2. If we eliminate the same number of majority numbers and non-majority numbers, the majority number still has larger frequencies than other numbers.
3. If a cnt turns into 0, it means we have met the same number of majority numbers and non-majority numbers.

n/2

Given a non-empty array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

int cnt = 0;
int cand = ll{INT_MIN} - 1;
for (auto num : nums) {
    if (num == cand) {
        cnt++;
    } else if (cnt == 0) {
        cand = num;
        cnt = 1;  
    } else {
        cnt--;
    }
}

n/3

Given a non-empty array of size n, find all majority elements. The majority element is the element that appears more than ⌊ n/3 ⌋ times.

The order of branches are extremely tricky here.

The correct order should avoid cand0 and cand1 get the same value, so at first we should check if the current value is in the two candidates or not.

ll cand0 = ll{INT_MIN} - 1, cnt0 = 0;
ll cand1 = ll{INT_MIN} - 1, cnt1 = 0;

for (auto num : nums) {
    if (cand1 == num) {
        cnt1++;
    } else if (cand0 == num) {
        cnt0++;
    } else if (cnt1 == 0) {
        cand1 = num;
        cnt1 = 1;
    } else if (cnt0 == 0) {
        cand0 = num;
        cnt0 = 1;
    } else {
        cnt0--;
        cnt1--;
    }
}

The following order will fail in case [1,2,2,3,2,1,1,3]. Since at index 3, cnt1 will turn into 0, so at index4 cnt1 will be the 2, which causes duplication.

for (auto num : nums) {
    if (cand1 == num) {
        cnt1++;
    }  else if (cnt1 == 0) {
        cand1 = num;
        cnt1 = 1;
    } else if (cand0 == num) {
        cnt0++;
    } else if (cnt0 == 0) {
        cand0 = num;
        cnt0 = 1;
    } else {
        cnt0--;
        cnt1--;
    }
}