Boyer Moore Majority Vote Algorithm

[@aliyazdizadeh]

I was so confused since I could see many examples where this fails but there 2 important things here: 1. If there is no majority element it will return some wrong value 2. So there has to be a verification step at the end which is also O(n)

[@chitalvision]

I have been through a lot of explanations for this problem. Yours has been the easiest to understand and follow through.

[@Texa8]

Instead of 2, 1, 2, 2, 2, 1, 1, 3, 2 if the array was 2, 1, 2, 2, 2, 1, 1, 3, 3, it would give the majority element as 3... At least according to your definition, which to me seems incorrect

[@mapl3man237]

In this problem you assume that a majority element always exists, if there were only four 2s there wouldn't be a majority element.

[@anujonthemove]

A much better explanation than most others on YT.

[@AlgosWithMichael]

Hey thanks

[@hhjdkdnchidnd]

Totally agree, really good presentation

[@Aditya-jv9mp]

I'll be patiently waiting for you too have 100k+ subscribers! I love your content. I'm part of the early notification squad!

[@AlgosWithMichael]

That is very nice of you, thank you for the encouragement!

[@noodlespwn42]

Your explanation and code don't add up. Can you please explain why we can skip the element that takes the count back to 0 as a majority element candidate? It looks like that's what your solution is saying. Either that or can you provide a solution that actually goes inline with your algorithm explanation? Any help is appreciated.

[@xnl3358]

for the example of 2, 1, 2, 2, 2, 1, 1, 3, 2... base on the code you write. after the first "1" at index 1. before, moving to index 2, the candidate is still 2, but the count will be 0 correct? it won't change to candidate 1, count 1

[@julianguyen7200]

this

[@saulgoodman6710]

It shouldnt matter since we're foccused on values which are majority in number not the one which are equal.

[@araneuskyuro]

Fantastic explanantion, thanks mate

[@neobrute-ek1bf]

An addition to verify if the candidate is really the majority element: We go through the array a second time and only count how often the candidate element (we found in the first run) is in the list. When we count it over N/2 times, then it is really the majority element, if not then we know there is no majority element in this list. Since we only have two runs through the array, we have 2*N comparisons, means its still linear runtime O(n).

[@AlgosWithMichael]

Pro explanation

[@mozabbbas]

I think you need to implement verification phase also By Reset count to 0. Traverse the array again to count the occurrences of the candidate.

[@mozabbbas]

Consider the input array: [1, 2, 3, 4, 5, 6, 7, 8, 8, 8, 8]. In this array, there is no majority element because no element appears more than ⌊11/2⌋ = 5 times. Your code might return 8 as the candidate, even though 8 does not appear more than half the time. This is reason you need to add verification phase

[@captainmcduckyYT]

Thanks so much Michael

[@AlgosWithMichael]

No problem

[@meiantv9191]

in turkish we say that, "Explaining it as if you were telling it to an idiot. ". Thank you so much.

[@DWEthiopia]

So I believe this algorithm ONLY works if it is given that each test case WILL HAVE GUARANTEED majority element. It wouldn't work if there wasn't a majority element. You clarified this in your video but just wanted to highlight how important that is.

[@AlgosWithMichael]

Yep, thanks for highlighting the importance of that!

[@ankitsingh-vg5uf]

Hands down, one of the best channel

[@AlgosWithMichael]

Thank you very much, that means alot

[@heisenberg1844]

Another great video. Thanks a lot.

[@AustinCS]

at 2:12 the order is messed up.

[@manuj9570]

Your channel is so underrated !

[@AlgosWithMichael]

Thank you!

[@englishonlyhere]

Thanks! I like very much your channel!

[@AlgosWithMichael]

Thank you!

[@kingofgods898]

Fucking brilliant. Great presentation as well. Good shit Muinos!

[@AlgosWithMichael]

I appreciate that!

[@lostmeme9862]

I already caught the hare, how much more of this is out there.

[@abhijit-sarkar]

Note that the comparisons are made between the current element and the candidate, _not_ between the current element and the previous element. If you miss this crucial point, you're going to get the algorithm wrong.

[@pramodsharma4508]

Great work...keep posting such videos...your channel will definitely grow..

[@AlgosWithMichael]

Thanks a ton

[@MayaBello]

you are incredible at explaining these concepts 😭👏🏿👏🏿👏🏿

[@AlgosWithMichael]

Thank you very much!

[@9392539968]

some thing is wrong in this code if you have 1,3,3,3,4,4,2 you get output as 2 but it should be 3

[@SasiKutti]

Reason is, there is no majority element in 1,3,3,3,4,4,2. Since there are 7 elements in that array, a majority element should occur at least 4 times, but no element in the array occurs at least 4 times. As he mentions at 3:50, this algorithm works only if the array does have a majority element.

[@kunal_chand]

​@@SasiKutti Yes makes sense. And to detect the "no majority element case", we can iterate through the array again and check if the occurrence of the element (that we got at the end of the previous iteration) is greater than n/2.

[@elpelicanojiji]

the java code is missing a final verification that the CANDIDATE COUNT is more than N/2, right? But still if the input would be for example: 1,2,1,2,1,2,1,2,1,2 the result would be 2 but the count would be 1, there is no way to assess its really a majority. Im confused, wouldnt it be more strict to keep a count of every element in a hash table?

[@theghostwhowalk]

Simple but can be tricky o(1) space in interview 😀

[@AlgosWithMichael]

Yea, definitely a bit tricky

[@sontran6673]

If i have a array = [2,2,2,2,1,3,4,5,6]. That algorithm is correct ?

[@jjkoh2495]

No, because there is no majority element which is a given condition

[@johntown4671]

nice implementation but it does not work for a simple array of just [1,2]. The code should return None or Null because there is no majority. For this to work one needs to add code to re-count the candidate in the array and compare it to the floor of n/2 ( or n // 2 ) Then return the candidate if indeed the count > n // 2

[@hariniravichandran4059]

Pls do some videos regarding Data structures and algorithms 😭 !!

[@AlgosWithMichael]

Yep many more to come

[@kevinoliveira7194]

Hi, can you give me a hand if where this algorithm is usually applied?

[@a4rdev]

TY

[@tathagatnegi5923]

Thanks👍

[@AlgosWithMichael]

No problem 👍

[@sarthakmanojade4887]

A small optimization could be to not update the candidate at the same index where count becomes zero, but on the next element. Just reduces a few operations that's all

[@princerajput9302]

Your teaching style is fabulous. Love from India.

[@saichennu5288]

Bro please upload some dp based problems

[@AlgosWithMichael]

Definitely man

[@sameer9368]

You are the best...I am from India...plz post such coding video regularly

[@NghiaTran-er5mp]

Your explain is not cover enough how this algo work. You just point out the easiest case without bring out the myth behind or some defense for all cases. Not convincing to me.

[@AlgosWithMichael]

The point of this video was not to go over a proof, but to understand the algorithm itself. A follow up video could be done though to elaborate on why this works in all cases, thanks for the feedback