Moore voting algorithm

This video explains the most efficient algorithm to find majority element in an array. In this video, i have explained the moore's voting algorithm along with intuition behind the algorithm. First i have explained the algorithm and then explained why the algo will work and finally shown the CODE for it. CODE LINK is present below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.com/SuryaPratapK/...
Majority element in an array using BitMasking: • Majority element in an...

[@raghavkakar8092]

The intuition behind is basically pigeon hole principle, as you'll always have count>=1 (for the majority element) after cancelling with all other elements.

[@abhijeetmohansingh4381]

yup

[@abhijeetmohansingh4381]

well that is quite helpful

[@sahilamrutagashe1696]

Thanks brother 😊🙏

[@timg8257]

I’m new to coding. How would someone attempt this in python in a simple and intuitive example?

[@anuragmalhotra2855]

What an exquisite way of explaining such a tough algo.. Keep it up ..

[@prabhakarkmr0]

you explained so well that i didn't have to look at your code , just listened to you like a story and code it myself and it got submitted in 2 go.thanks a lot for the clearity.Peace.

[@techdose4u]

Nice :)

[@jlecampana]

Great video! This problem just recently appeared in a Google Phone Screen, it's a very useful algorithm to have in one's toolkit!

[@SolutionHunterz]

Thanks for the awesome explanation!

[@techdose4u]

Welcome bro :)

[@mohamedsayed8697]

Thanks, this is really helpful.

[@annas8308]

Your teaching is great!

[@techdose4u]

Thanks :)

[@GAURAVJEETSINGH1]

Amazing explanation!

[@vasushrivastava4578]

the explanation is just perfect. thanks :p

[@techdose4u]

Welcome :)

[@rahuldeshpande3516]

Its simple yet incredibly genius

[@samjason324]

Amazing, I understand the algorithm after watching first 3 minutes of the video.

[@techdose4u]

Thanks 😊

[@freshcontent3729]

@dheer jain bro but what if the interveiwer asks .. "tell honestly.. u knew the algo from before right ? then why did you act like you didnt? " .. then in this case what do we say if such a situatation or a smiliar one arises.

[@mj-sv7ep]

Thank you, this helped me understand the algo. A minor fix at 1:30 - we should refer to the starting element as zeroth element and not as first element.

[@Idanh]

Hi, Thanks for this great explanation. That being said, I think that the code you suggest in findCandidate has a "redundant part" (yet it's correct). Inside the for loop, you first check if the current element equals to the majority element to increase or decrease the counter, and afterwards check the counter for zero to assign new potential candidate. Suppose we have 3 3 2 4 6, then in your code 4 element becomes a candidate despite there's no reason for it (4 isn't different from 2 for that manner). Only the next element should be considered as potential majority element. As I said it doesn't effect correctness, but yet I think it making more sense this way (and also wiki supports this). The code inside the for loop should be: if (count == 0) { ... (as it now) } else { if (a[maj_index) != a[i]) ... (as it now) }

[@techdose4u]

Need to check it :) Thanks for your suggestion

[@freshcontent3729]

@dheer jain bro but what if the interveiwer asks .. "tell honestly.. u knew the algo from before right ? then why did you act like you didnt? " .. then in this case what do we say if such a situatation or a smiliar one arises. Becacuse it's obivious ki one cant come up with such a solution so fast in the interview moment

[@joseph2073]

@@freshcontent3729 hey did u find a solution to this ? what should u say ?

[@yashgoswami5374]

@@freshcontent3729 I'm thinking that who ever is getting placed , they must know all the solutions of the problems which are beeing asked, because It's' nearly impossible to come up with such soln untill you haven't atleast go through it once

[@krishnendumandal6547]

This point is important Because when you will try to solve its extended version (leetcode 229) the approach in the video fall apart. You need to assign the new value only on count==0 to make it work.

[@doge-coin]

Nice video, thank you sir!!

[@techdose4u]

Welcome :)

[@priyachaturvedi9381]

Awesome explanation!

[@techdose4u]

Thanks :)

[@AmanKumar-xw5kl]

simply awesome.. you are doing great job sir..

[@techdose4u]

Thanks :)

[@harshpanwar1550]

Thanks a lot!!!!! That was amazinggggg

[@techdose4u]

Welcome :)

[@freshcontent3729]

@dheer jain bro but what if the interveiwer asks .. "tell honestly.. u knew the algo from before right ? then why did you act like you didnt? " .. then in this case what do we say if such a situatation or a smiliar one arises. Becacuse it's obivious ki one cant come up with such a solution so fast in the interview moment

[@martinharris4416]

Im becoming fan of your explanations

[@techdose4u]

Woww ❤️

[@samagrashukla]

good explaination, thanks!

[@techdose4u]

Welcome

[@ahnissingh6911]

Smooth and clear

[@shaurya478]

Very nice explanation... Thanks

[@techdose4u]

Welcome :)

[@nikhitham4815]

Thank you!

[@tsupreetsingh]

Good explanation

[@andiamakaza24]

Nice explanation sir

[@DiaryOfMuhib]

Awesome explanation bro

[@techdose4u]

Thanks

[@nskkknagajayanth1199]

Super Explanation 😃

[@techdose4u]

Thanks :)

[@riteshsaha6881]

This is so clever.

[@arthamsreenivas8858]

nice video and good explanation

[@techdose4u]

Thanks :)

[@arpitmani6553]

if we need to find elements which appears more than N/k where 0

[@techdose4u]

You can see this algorithm on stack overflow. For N/K.

[@arpitmani6553]

@@techdose4u OK.....THANKS SIR

[@APragmaticProgrammer-yl5pm]

great video

[@sarthakbhatia7639]

So this is my first video on your channel...Nice explanation!...Subscribed

[@techdose4u]

Thanks :)

[@dhruvagarwal882]

very nice explanation

[@techdose4u]

Thanks :)

[@dorisli3461]

omg best one i've seen on Moore's voting algorithm!!

[@techdose4u]

Thanks :)

[@harshavardhan2775]

Neat explanation.

[@techdose4u]

Thanks 😊

[@kongzilla2897]

Nice Thanks :)

[@techdose4u]

Welcome :)

[@code7434]

Amazing Man

[@techdose4u]

Thanks :)

[@code7434]

@@techdose4u Please add more interview problems

[@devanshgoel3433]

thank u sir

[@xixnecroxix]

very good explanation

[@techdose4u]

Thanks

[@freshcontent3729]

@dheer jain bro but what if the interveiwer asks .. "tell honestly.. u knew the algo from before right ? then why did you act like you didnt? " .. then in this case what do we say if such a situatation or a smiliar one arises.

[@priyanshigupta1359]

very nice expalanation

[@techdose4u]

Thanks :)

[@gouthamsidhardha681]

that was nice xD

[@techdose4u]

Thanks :)

[@neerajmahapatra5239]

Understood❤

[@rajeevcbhatia]

Thank you for the explanation! I have a question. Will it work for this array? [3,2,3] my understanding is that the steps will be this way:- 1. index 0, majority = 3, count = 1 2. index 1, element != majority so count--, count is 0 now so new majority is 2 and count is 1 3. index 2, element != majority so count--, count is 0 now so new majority is 3 and count is 1 at the end the count is not greater than n/2, which is 1 so this is not considered the majority. am i missing something here? Would appreciate the clarity :)

[@techdose4u]

Yes....you are long at last step. Doesn't matter what the count value is, the element in majority variable is the candidate for being majority element if any. So the next step is to verify by counting the frequency of leftover element in majority that is 3 here. You see it occurs 2 times and so it is majority. So this is a 2 times traversal process.

[@rajeevcbhatia]

@@techdose4u got it, thank you!

[@apoorvamittal1379]

When count becomes 0, why do we make the current element as the majority element? For example, at 3 the count becomes 0, so the majority element should be updated to the next element (4) and then the count should be incremented to 1? Does this not make any difference?

[@freshcontent3729]

@dheer jain bro but what if the interveiwer asks .. "tell honestly.. u knew the algo from before right ? then why did you act like you didnt? " .. then in this case what do we say if such a situatation or a smiliar one arises. Becacuse it's obivious ki one cant come up with such a solution so fast in the interview moment

[@siddharthkalani7535]

i see your explanation and seeing the comments below people do understand, but I didn't get it. ho wit works in [1,2,1,2,1] or [3,2,3,3,4]

[@techdose4u]

2 cancels 2 again 2 cancels 1 and finally candidate left is only 1. Now we again traverse the array and check if the candidate 1 is occuring for more than N/2 times. If yes then 1 is majority element otherwise there is no majority element.

[@dheerjain2884]

@TECH DOSE in an interview, Do we name the algo when we explain the approach to the interviewer? Like in this , its a Moore voting algorithm.

[@techdose4u]

No. Avoid naming algos.

[@dheerjain2884]

@@techdose4u Thanks for such a speedy reply. So when we explain the algo and then the intuition behind it, Wont the interview have some suspicion as these algos cannot strike at the moment. You need to know the working beforehand.

[@techdose4u]

He will obviously be knowing it. If he asks the name then tell him otherwise you shouldn't because he might ask some related questions which you won't be knowing.

[@dheerjain2884]

@@techdose4u True that. Thanks!!!

[@techdose4u]

@@dheerjain2884 welcome

[@varunoyal87]

Thanks for the explanation , I have one query in between 5:10 to 5:30 in worst case of 2,3,7,3,4 ME returns 4 as ME but its not so how we should handle this case I did not understand. Can you please explain a little more. Thanks alot

[@techdose4u]

As I said, if you have a majority element then you will get correct result in ME else not. So, whatever you get in ME needs to be verified by counting the occurence by traversing the array again.

[@varunoyal87]

@@techdose4u okay thanks . so there is a need to traverse again to verified the element.

[@freshcontent3729]

@dheer jain broo but what if the interveiwer asks .. "tell honestly.. u knew the algo from before right ? then why did you act like you didnt? " .. then in this case what do we say if such a situatation or a smiliar one arises. Becacuse it's obivious ki one cant come up with such a solution so fast in the interview moment

[@AmirAli-gv7kn]

@@varunoyal87 no, you don't have to traverse it again. Since, you already have a counter variable alongside. And 3 also does not satisfy majority element criteria which is greater than n/2 (in case of 5 element the majority element has to appear more than 2 times) which didn't happen in the above example

[@dmitriy_dokshin]

You don't need to set element when count becomes 0, if current value is the majority element next iteration will fix that.

[@suraj_meena_505]

For me this video actually began at 3:29 "so why this technique is actually working ?" though I was not so convinced with later part

[@techdose4u]

It works because if we have majority element then if we try to cancel one element with another different element, no matter in what order, the majority element will remain. The first pass only finds the candidate for being a majority element and then we verify in the second pass if the candidate is actually the majority element. Take examples to understand clearly.

[@suraj_meena_505]

@@techdose4u thanks for reply...I got it now

[@varunnarayanan8720]

@@techdose4u Yes this one line explains the why very well. Thanks.

[@abhishekks6782]

What is the time complexity and space complexity of this code?

[@thewatcherlollol]

O(N) time complexity and O(1) space complexity.

[@godlevelchoker4543]

Tip: more's voting algorithm + mapping , time complexity will be better than anyone

[@techdose4u]

👍🏽

[@godlevelchoker4543]

​@@techdose4u i appreciate your video , thank you bro

[@a036nikhilsannat4]

How to prove this algorithm?

[@AdityaLSharma]

Wondering how many years would it take for me to explain concept with such clarity lol

[@sachinnegi8814]

What if we sort the array and get the middle element.

[@techdose4u]

You can do that. But it is not the most efficient process and also if the array is immutable, you can't do that.

[@SR-we1vl]

@TECH DOSE Does the relation is greater than N/2 or greater than and equal to N/2 elements!?

[@techdose4u]

Greater than N/2

[@SR-we1vl]

@@techdose4u Thanks!

[@AJAYPAL-zu6lg]

{2,1,2,2,2,3} n=6 and candidate element. Is 3 but 2 is a ME which present

[@arpit39agarwal]

So in this case you have taken {1,3,3,1,2} so no majority element right ?

[@techdose4u]

Yes right

[@tejitha6762]

If the question is of n/3 and the array is[1,1,1,2,3,4,7] then ?

[@techdose4u]

This problem is not solved using this algo. There is a generalized algo for N/K which is very well explained on stackoverflow. I will explain that in future.

[@namanagrawal4868]

@@techdose4u please make a video on that as well

[@nikhilpandey3486]

@@techdose4u But then it is giving wrong ans

[@kirtigera2225]

Sir please make video on segment tree and lazy propagation

[@techdose4u]

Many people are requesting the same. I guess i have no choice now but to make it. Will upload it surely in coming month. I have added it in todo list.

[@mohitlalwani3505]

is this algo work for N/3 repeat.

[@techdose4u]

Nope. It works for Freq > N/2

[@sed6845]

Hi, can you tell me why the majority element is a problem ?? what will happen if we have majority element in an array ??

[@techdose4u]

Good question. Let's say there are many contestents in a pool, standing for the same postion. Then people might VOTE for anyone. Now let's assume the sequence of VOTEs casted by people forms an array. Now, your criteria to select the winning person is by majority VOTE. So, you will find the majority element in the array. This is one simple example.

[@sed6845]

@@techdose4u thank you very much. :)))) I got it now.

[@techdose4u]

Welcome :)

[@abhishekchoudhary8023]

2 pointer se bhi ho jayega

[@areshbabu]

Does this algorithm works for the following array {1, 1, 1, 2, 3, 5, 7} Count becomes zero for the majority element 1 by end of the array. And once the count becomes zero we change the majority element to 7 and return it. In the next step, if you find the frequency of 7, then its less than n/2 times and we return the output as no majority element. That is incorrect output. Please correct me if my understanding is wrong.

[@tushargahlaut5812]

For Majority Elements, the count should be greater than N/2, like if N=7, then N/2=3 (integer), so your majority element (let's say 1) should occur at least 4 times, so the algorithm is correct.

[@areshbabu]

Thanks @Tushar Gahlaut for giving the clarity. I was trying for n/3 scenario which may not work in this case.

[@evantilley]

Thank you! Was wondering why the complexity is 2*N? I get we have to traverse it once since we're looping through the array, but where is the second traversal coming from?

[@techdose4u]

1st traversal is to find the candidate. 2nd traversal is to verify if candidate is majority element.

[@evantilley]

@@techdose4u ah okay thank you!

[@jasdfpasdfakdsjhfa]

@@techdose4u Oh gotcha, but this is to verify only right? For example in a question on leetcode, they guarantee that the array passed does contain a majority element, therefore we only need to return the candidate.

[@aayush5474]

this wont work if ME is > n/3 right?

[@techdose4u]

Yes. This is only for >N/2.

[@abhireddy8164]

Sir please make a video on dice throw problem sir

[@techdose4u]

I have queued your problem in to-do list. Will upload it in Feb.

[@nikhilpandey3486]

It fails for the case(the condition is greater than n/3) 1, 1, 1, 2, 3, 5, 7 Here the program return -1 but the ans is 1

[@ayusharyan683]

total element in the array is 7. Acc to the algo. count of 1 must be greater than n/2 i.e 3 than it'll be answer. But here count of 1 is not greater than 3. So answer is -1.

[@user-nf2br1mu6o]

What if there's more than one majority element?

[@aisharawat9102]

Do elements ki Freq n/2 se zaada nhi ho sktii....vo to greater than 2(n/2) ho jaaega means greater than n (size of the array)

[@babitakumari2315]

candidate element will always be the one that occcurs maximum no of times ???

[@techdose4u]

No that is not tru....consider 1,1,1,2,3,4,5. Here 1 occurs the most times but candidate will be 5. If there is a majority element then candidate will be the majority element for sure otherwise any random element can become the candidate (probably from the ones occuring near the right end).

[@babitakumari2315]

@@techdose4u thanks

[@SurajRaj-vh5ei]

1, 2, 3, 4, 1, 6, 1, 7, 1, 7 For the above input. I don't thik this will work. It will return 7 as majorelement. But it should be 1. Can you please explain the above input that if I'm missing something.

[@techdose4u]

There is no majority element. After finding candidate element, you need to traverse again and find the count of that element in the array and see if it occurs for more than N/2 times. Then only it will be a majority element.

[@SurajRaj-vh5ei]

Thanks. But for this input, candidate element will be 7 by the provided algorithm, not 1. So the function will return -1 as output but it should be 1. As 1 is repeated 4 times.

[@MrAkshat7]

@@SurajRaj-vh5ei Bro, this array doesn't have a majority element. 1 occurs 4 times but the definition of majority element is that the element which occurs more than floor(n/2) times (which is 5 for your array) is the ME. So the algorithm is valid.

[@aishiksarkar8226]

What if two 3s were not consecutive?

[@techdose4u]

It wouldn't matter

[@abhinavgarg5611]

Simple Explanation (Majority Element occurs in following 2 cases only) 1. Element occurs consecutively for more than n/2 times 2. Element occurs non-consecutively for more than n/2 times In either of above 2 cases i.e. if we assume that frequency =n/2 +k , (k>=1) the remaining n/2-k , (k>=1) elements won't be able to cancel the frequency of majority element. Hence we always get a majority element.

[@techdose4u]

👍🏼

[@freshcontent3729]

@dheer jain bro but what if the interveiwer asks .. "tell honestly.. u knew the algo from before right ? then why did you act like you didnt? " .. then in this case what do we say if such a situatation or a smiliar one arises. Becacuse it's obivious ki one cant come up with such a solution so fast in the interview moment

[@easward]

What if the array is 2 3 2 4 2 ?

[@watcher5232]

Works fine. 2 is the majority element and its frequency is > n/2

[@gopinath7846]

can u possible try to solve this probelm "tomorrow" to "ooorrtmw"

[@techdose4u]

??

[@gopinath7846]

@@techdose4u it say that o was 3 times times repeated r is 2 times repeated in the way we want to show the output like

[@freshcontent3729]

@dheer jain bro but what if the interveiwer asks .. "tell honestly.. u knew the algo from before right ? then why did you act like you didnt? " .. then in this case what do we say if such a situatation or a smiliar one arises. Becacuse it's obivious ki one cant come up with such a solution so fast in the interview moment

[@manojpokhriyal1183]

Please take the case [2,2,2,2,4,2,5,3]...the should be 2 but according to this algo if we go..we will get count =4 upto fourth 2 , then 2 not equal to 4 count=3 , then 4 !=2 , count=2...2!=5 count=1 , ....5!=3 count =0...when count become 0 we update majority element by 3 and make count =1 ... So it will verify for 3 not 2 ...please clear this doubt.

[@abhaytiwari6411]

fabulus video make video on this type of topics

[@techdose4u]

Keep suggesting topics :)

[@abhaytiwari6411]

OK Bro

[@amanrubey]

better than gfg!

[@soneshengg]

Thanks!

[@dheerajpoonia2175]

1 3 2 3 5 3 4 5 3 2 3 2 3 5 Sir algorithm not working for these test cases why ?

[@techdose4u]

Its working perfectly fine bro. Majority element is always greater than N/2. In both test cases, you don't have majority element. Please rewatch the video carefully.

[@dheerajpoonia2175]

But sir in second test case 3 is occurring 3 time so 3>=6/2

[@dheerajpoonia2175]

And my other doubt is that "Moore voting algorithm is work when n/2 is not given and we have to find majority elements from complete array"

[@techdose4u]

@@dheerajpoonia2175 but majority means > N/2. Haven't I told this in the video?

[@techdose4u]

@@dheerajpoonia2175 we dont need to find for N/2 and that's why it is an algo.

[@bajisyed9532]

This is failing for the input {2,2,2,3,4,4}

[@ijaz2020]

847. Shortest Path Visiting All Nodes this pblm pls

[@techdose4u]

Can you please provide a link explaining the problem statement.

[@ijaz2020]

@@techdose4u leetcode.com/problems/shortest-path-visiting-all-nodes/

[@techdose4u]

Queued 👍

[@Shivam_Manswalia]

python: class Solution: def majorityElement(self, nums: List[int]) -> int: nums.sort() return nums[len(nums)//2]

[@techdose4u]

Thanks for sharing

[@techdose4u]

Correct

[@abhishekmerotha9928]

what about 1 2 1 3

[@techdose4u]

Nothing is Majority in this case.

[@sandeepkumawat4982]

Please make a video on n/3 repeat element🙏🙏

[@techdose4u]

Good question. I will try as soon as I get time.

[@nikhil.pandey]

@@techdose4u please make it sir!

[@j.y.]

azyum are is sorted fost

[@easward]

Simpler way is If element at first and last are not same then an element has to occur consecutively else there is no such majority element.

[@tashifhoda2414]

Another way to visualize why this algorithm works is to think of an array of any size (say 6). Now try to fill it in with an element such that this element becomes the majority element. For our example a number x has to appear at least 4 times in the array to be able to satisfy the criteria of being a majority element. You will see that there is no way you can fill in the the number without it occuring consecutively, at least once in the array. This very fact is what makes this algorithm work.

[@MrJiJoJu]

No need for the number to occur consecutively, for example in 13131, 1 is majority but there no two consecutive 1.

[@tashifhoda2414]

@@MrJiJoJu 1 is not the majority element in your example because it appears exactly n/2 times (3 times). It has to appear 4 times to be the majority element.

[@MrJiJoJu]

@@tashifhoda2414 In my example there are 5 elements, and 1 appears 3 times (3 > 5/2)..3 is a majority in an array of 5 elements

[@tashifhoda2414]

@@MrJiJoJu Ohh, my bad then. This is a very valid counterexample. Thanks. Looks like I need to update my intuition ^_^

[@igaming_]

This fails for 2,3,2,4,2

[@iamnotahuman2172]

No it does not

[@saravanansivakumar9259]

2 is the majority candidate at last with count 1. So 2 is the correct answer and it does