# 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--;
}
}``````