# Boyer-Moore Majority Vote algorithm generalization

• Boyer-Moore Majority Vote algorithm generalization to elements appear more than floor(n/k) times

``````class Solution {
public:
vector<int> majorityElement(vector<int> &a) {
int y = 0, z = 1, cy = 0, cz = 0;
for (auto x: a) {
if (x == y) cy++;
else if (x == z) cz++;
else if (! cy) y = x, cy = 1;
else if (! cz) z = x, cz = 1;
else cy--, cz--;
}
cy = cz = 0;
for (auto x: a)
if (x == y) cy++;
else if (x == z) cz++;
vector<int> r;
if (cy > a.size()/3) r.push_back(y);
if (cz > a.size()/3) r.push_back(z);
return r;
}
};``````

• Hi, MaskRay. Thank you for your sharing. Could you give some explanations for the above code or provide some links w.r.t the algorithm? Thanks!

• At most have two numbers appear more than 1/3,If a number's frequent >1/3,then it must have recorded as y or z,because other number's frequent <1/3,they cann't minus y or z out.

• Hi, johnlao. Thank you. I have got the idea.

• for java form

``````public class Solution {
public List<Integer> majorityElement(int[] nums) {
//there should be at most 2 different elements in nums more than n/3
//so we can find at most 2 elements based on Boyer-Moore Majority Vote algo
List<Integer> res = new ArrayList<Integer>();
if(nums.length==0) return res;
int count1=0,count2=0,m1=0,m2=0;
for(int n : nums){
if(m1==n) count1++;
else if(m2==n) count2++;
else if(count1==0) {
m1=n;
count1=1;
}
else if(count2==0) {
m2=n;
count2=1;
}
else{
count1--;
count2--;
}
}
count1=0;
count2=0;
//count the number for the 2 elements
for(int n:nums){
if(n==m1) count1++;
else if(n==m2) count2++;
}
//if those appear more than n/3
return res;

}
}
``````

• Just curious, if we initialize y and z to the same value (e.g., 0), the above solution should still work, right?

• Hi, zhukov. I try it and it works.

• Thank jinchao for the confirmation. I have tried it and it worked, too. I think that if we initialize y and z to the same value (e.g., 0), the only special case is that the numbers are all 0 and it can still be properly handled by the second loop. Other cases are essentially handled in the same way as y and z are initialized to different values.

• Hi, zhukov. Thank you for your nice observations. Well, I have not thinked that deep as you do :-)

• This post is deleted!

• I have tested [51, 24, 24, 43, 24, 38, 32, 9] and the solution passed.

• Weird....it works this time...maybe I was wrong, sorry about that

• Hi all, the initial value of y=0 and z=1 seems not-so-easy-to-understand for me. So i changed the first for loop a little:

``````class Solution {
public:
vector<int> majorityElement(vector<int>& nums) {
vector<int> majorities;
int a, b, numa = 0, numb = 0;
for(auto x: nums) {
if (numa == 0) {
a = x;
numa = 1;
} else if (x == a) {
numa++;
} else if (numb == 0) {
b = x;
numb = 1;
} else if (x == b) {
numb++;
} else {
numa--;
numb--;
}
}
numa = numb = 0;
for(auto x: nums) {
if (x == a) {
numa++;
} else if (x == b) {
numb++;
}
}
if (numa > nums.size()/3) {
majorities.push_back(a);
}
if (numb > nums.size()/3) {
majorities.push_back(b);
}
return majorities;
}
};
``````

• Hi MaskRay, I don't think your generalized algorithm works for any value "k" such that elements appear more than floor(n/k) times. You are assuming that the number of majority elements that can exists is atmost two for any value of "k" which is incorrect.
For example: if k = 4 and n=16 then there can be 3 majority elements each appearing 5 times correct?

• Hi,jianchao.li.fighter.I test your code, it will be wrong for this case:[1,2,2,3,2,1,1,3].I wonder if there is something wrong.

• Where did I post any code? The code is not mine...

• oh,sorry : )

Have been confused why `if (x==y) else if (x==z)` is done first and then `if (!cy) .. if (!cz)...` part? why not;

``````if (! cy) y = x, cy = 1;
else if (! cz) z = x, cz = 1;
else if (x == y) cy++;
else if (x == z) cz++;
``````

Can anyone elaborate?

• @leaper We should make sure y and z point to different numbers, if let `if (!cy) .. if (!cz)...` first at first y and z are both a[0], you can check this test case `[8,8,7,7,7]` for example.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.