Majority Element | Leetcode | C++ | Java | Brute-Better-Optimal | Moore's Voting Algorithm

[@takeUforward]

Please watch the new video which covers it in more depth, and also prints it: kzbin.info/www/bejne/pIHCn6ZpqribbpI We have updated a new video on the same topic, which covers it in more depth, and c++, java, and python codes as well. Find the video here: kzbin.info/www/bejne/pIHCn6ZpqribbpI

[@AnkitKumar-vd2dd]

yes

[@arpanbhowmick847]

Yes bhaiya

[@amitgusain9919]

Take it positive or negative way it's up to u vikram, I have seen u don't stop or ignore if someone says something to you, u are in early days of ur carrier one thing u should keep in mind if u wanna go long way, u should be gentle to ur viewers either they are ur hater or likes u, man these thing will keeping coming ur way the only thing which will keep going is ur behavior aur respect to ur senior or junior or anyone, I know ur hard working, knowledgeable and helping but ur nature or can say telling something which shows some negativity to ur viewers or friends will let u down, hope u understand keep doing good work, all the best.

[@takeUforward]

@@amitgusain9919 if someone comes and hits a dislike to a video right after uploading, I don't think I should be anyways responsible for them. I am responsible for the my takeUforward fam, not for haters gang ;)

[@codeWithRisingGeek]

@@takeUforward Understood the intuition behind the algorithm. Regarding the dislikes, I think if there was a scope of improvement, they would have watched the whole video and then hit that dislike button. This was not the case as you told. Anyways, great work!

[@nimishgupta8357]

The intuition was the key in this. Have read Moore algo many times but never had this much clearity 🍻

[@mayurkalsekar524]

I have lost the hope to come up with such intuitions on my own

[@renon3359]

Don't let anybody discourage you brother. You are doing an awesome job. I am going to like this video from all 4 accounts I have. Cheers!

[@ssv6055]

i am going to ruin those 69 likes buwahahaha

[@rohanbose4882]

Dislikes are from the scalar academy guys (because their turnover is made by selling these solutions ) :P

[@Onchaingambit]

Thanks man for giving out such quality content for free at expense of your valuable time 😊

[@dhanashreegodase4445]

You are teaching us such a valuable content for free of cost..thanks alotttttttttttttttttttttt

[@xD-qv6vs]

It's rare people tell about intuition behind their solution... bhaiya you are just so amazing!!! :)

[@AdityaKumar-rs5jn]

Yes understood..Finally got to know the intuition behind it.. Great explanation ..

[@harshitsrivastava3683]

Yes, I always use brute force approach to solve the problem, it works and i move ahead. Now I know, I am doing wrong. Thanks sir

[@adityasaxena3903]

Absolute Love. Amazed by this algo! Thanks, Striver for this.

[@ranasauravsingh]

UNDERSTOOD... !!! Thanks striver for the video... :)

[@suguruchhaya3194]

(To those who have skepticisim towards the Moore's algo) Striver probably said this somewhere but this is how I tell myself that the algorithm works and I will reiterate: The last segment ("5555" in striver's video) MUSTTTTT be contributing to the fact that a majority element exists. The reason is simple: without the last segment, there will not be a majority element which appears more than half of the time.The given array can only have a majority element IF AND ONLY IF the last segment tilts the balance and actually creates a majority element.

[@vibhor3049]

Guys, Moore's algo is based on the assumption that you have a majority element(i.e., count > floor(n/2)) in your list. So choose a input where there's definitely a majority element, otherwise you'd think this algo is not working.

[@KuldeepSingh-rw6ji]

I tried for input [2,2,3,3,3,4,4] and it is giving 4 instead of 3

[@kshitizagarwal8389]

Size is 7 According to the problem, majority element should occur more than thrice i.e. atleast 4 times. In your case, majority element (3) appeared only thrice.

[@ecea044gauravgogoi2]

your videos are short and precious , voice is awesome, how can somebody dislike it

[@emilyghosh8679]

Excellent explanation ❤loved it

[@aasthajha1051]

raj bhaiya hai toh concept clear hone se koi nahi rok sakta!!!!!! thank you so much for this crystal clear explanation!!

[@sahukarinaveenkumar3188]

Bro don't think about such people, you are really helping alot for us..

[@ROHITSINGH-td9ms]

Arrey bro!! Infact it was your set of codes on gfg(height f tree, etc.) , we look at when it comes to the interviews. Plz don't stop here. Great work 👍

[@sachinsoma5757]

Please ignore hate comments, your videos are really helping and we are really learning from you .

[@NatureLover-oq6uc]

MAN YOU HAVE ENTIRELY CHANGED THE CODING ATMOSPHERE IN THE COLLEGES....NOW EVERYONE IS ACCESSIBLE TO A GOOD CONTENT.

[@chiragmehta2955]

best explaination so far ........especially that text at 9:41 proves that mathematically. thank you

[@walkalone1998]

Numbers occupying more than half the space must be in the middle when sorted class Solution { public: int majorityElement(vector& nums) { sort(nums.begin(), nums.end()); return nums[nums.size()/2]; } };

[@aasmohammad2651]

no one can stop you bcs you are doing a great job without any greed,

[@somyapratapsingh9849]

Your videos make me thing ds and algo are very easy. Hats off to u 👏👏

[@debjitmaji632]

If someone still doesn't understand do refer GFG... Very nice explanation

[@rishigupta4938]

best dsa sheet and solutions till now,highly appreciable 🙌

[@bhaveshkumar6441]

You're the best teacher on this planet. Thank you for explaining this so clearly

[@shubhamsingh-hp3dk]

this helped me a lot in an assignment

[@shiershdwivedi9268]

Yes, You are taking us forward!

[@mdbahauddin1252]

thanks 'striver' for helping us , please ignore them who dislike your videos. They are nothing but always spoil the life of other because they never taste the success of any kind . We are with you ! keep it up! :)

[@aniketshukla8085]

The C++ code shown by striver(09:53 Mins), assumes that if majority element is not present in prefix then it is going to be the last value of "candidate". For example: If we put input array as: 7 7 5 7 5 1 5 7 5 5 7 7 10 10 10 10 Answer is going to be : 10. This would be true for variant of same question which says that, there always exist a majority element and till last element if we are not able to find the majority element then it would be last element.

[@aniketshukla8085]

The other video which has been made by striver on same question(link is pinned in first comment) returns - 1 if there does not exist any majority element at all.

[@rryann088]

this simplifies a lot int majorityElement(vector& nums) { sort(nums.begin() , nums.end()); return nums[ (int)nums.size()/2 ]; } Thanks

[@takeUforward]

And this guarantees that you will be rejected in an interview if you say this even after knowing the solution in video!

[@rryann088]

@@takeUforward Is it because of the simplicity of this code or because of not implementing the moores algorithm? Thank you !! I just want to know why I will be rejected in this particular context

[@NehaKumari-cx6un]

Whoever dislike ur videos r not student.. They are ur competitors . So keep making videos👍👍

[@stith_pragya]

Thank You So Much Striver Brother...................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@the3idiots787]

such a great explanation .First year student like me are able to understand it clearly.

[@vijaykumar-sl7rp]

Those words during the first one minute! 🔥🔥🔥

[@yashrajput7386]

If it is not specified that there exist majority element then, There is a catch with this solution it will return the majority element in the last suffix example if arr[]={1,1,2,2,3,3}, returned candidate will be 3 but this is not the majority element Therefore it will become half of the correct solution, finally after the end of for loop in this solution once again count the number of occurrences of candidate element in array and check if it is >floor(n/2) to confirm its majority

[@vikasmahajan9602]

bro it is mentioned that there will always be a majority element present

[@madhubabu3938]

Another approach:: Sort the array and return the middle element (because majority element occurs more than n/2 times in array that means after sorting middle element must be the majority element) Time - O(nlogn) Not best but better than bruteforce

[@takeUforward]

Yes, true that !

[@madhubabu3938]

yeah,Kuldeep Singh. But Striver already discussed that approach in the video.

[@jatinranpariya1510]

TC can be O(n). Remember we only need to find middle element So we don't have to sort whole array. This can be done using nth_element() library function in O(n). Basically nth_element() is an STL algorithm which rearranges the list in such a way such that the element at the nth position is the one which should be at that position if we sort the list. class Solution { public: int majorityElement(vector &nums) { nth_element(nums.begin(), nums.begin() + nums.size() / 2, nums.end()); return nums[nums.size() / 2]; } };

[@Sweety-rx8zq]

Woww great🙌 actually must not care about those who dislikes such great content

[@manaswitadatta]

I feel in love with this algo when I saw it the first time. 🖤

[@tonystarc9567]

Brother you are a saviour... Thank you for every thing... Just one more thing brother if you could continue bringing atleast 1 video per day then it would be a lot of help... Thank you...

[@leapingquark]

The way you let go of all the negativity at the beginning of the video was amazing. You are going a very good job bhaiya, I have learned a lot from your videos. Don't ever let anyone discourage you!!

[@HarshKumar-nh6be]

There's no one who can not understand from you.. You are super genious😎😎

[@praffulbisht8520]

if your one test case is not running i.e. {3,3,4} Then after: if(count==0){ ele = nums[i]; //add count ++; also count++; }

[@AbhishekKumar-eh6zy]

sir your exaplanations are just awesome

[@learn9475]

salute explains it all about this man

[@anilsuyal]

No Dislike can stop my brother! you're amazing brother, huge respect:)

[@sagarchippa327]

Great Explanation👌of intuition behind Moore's Voting Algorithm.

[@Vishalraj_1]

I don't understand what they will get by disliking the video or demotivating others. Anyway, You are doing great job. Keep take us forward !!!!

[@Nikhil-qd9up]

I think using unordered_map will have T.C as O(n) ???

[@AdityaRaj-ix5rg]

The intuition you provided was awesome. Thanks for the video!!

[@sanskritisrivastava2242]

Best explanation! I never understood this concept so clearly until now.. Thankyou so much!!

[@gaunikasrivastava7851]

The person who would have come up with this algorithm might have been an absolute genius 🤯🤯

[@rohitraina5059]

I guess it was moore 👀

[@toshimudgal7288]

@@rohitraina5059 lol

[@abhisheksanwal1106]

No it is based on pigenhole principle. Idea has been taken from that.

[@ayushverma6131]

thank u soo much sir, I think this is the best explanation till now for moore voting algo. :)

[@youngshahrukhkhan8179]

Very Nice Explanation......Keep making videos

[@prakashsingh1107]

I love watching your content its awesome

[@darshantank554]

Good solution Bit masking is also a good solution but takes O(NlogN base2) time!

[@zafarkhan6242]

Awesome sir well explained this topic

[@bhaveshkumar6842]

Thank you so much for what you are doing!!! ❤️❤️❤️

[@krishgarg5665]

Before hashmap solution we can tell sorting solution. SOrt the array and check if nums[i]==nums[i+n/2]

[@anonymousvoid6356]

Striver bhaiyya!! Nice explanation!!!!

[@ishitakeshawani2997]

You are doing great work. Thank you 😇

[@VinayPandey-l9j]

Great explanation. Thanks

[@atibhu]

Beautifully explained!

[@wasimakram5371]

very detailed explanations ! Keep it up bro !

[@rhl_]

Best explaination. Thank you so much.

[@takeUforward]

Glad it was helpful!

[@avikumar9046]

Striver we all love you......Thanks for all your efforts for us sir..

[@yashrastogi3726]

Great explanation bro. Love this series. thanks

[@satyamgupta6030]

what an amazing video thanks a ton. Keep making such awesome videos.

[@SuryaPrakash-us6vn]

in hashmaping technique if we change the last three digits to some element x in above example then ........x will be shown as majority element

[@prachipadhi703]

Bhaiya , I owe u a lot , tq for the placement series...

[@riashrivastava5358]

bhaiya ,do not focus on hate .you don't even know how many lives you are changing .we will always be grateful

[@lovleshbhatt7797]

Reveal the name who gives dislike , we all try to ask them what is wrong with them. Btw awesome series bhai

[@archihalder7462]

Thank you so much for this great explanation

[@joeyaintwaffling]

There can be an edge case where the given array has a majority element but the count of the majority element is not more than n/2 like for this example : 3, 3, 4, 2, 4, 4, 2, 4 ; here n is 8 but the majority element according to moore's algorithm will give you 4 but 4 doesn't occur more than n/2 (4 occurs for exactly n/2) times hence the code will fail there. To overcome this write another loop from 0 to n and count the occurrence of candidate element which you got from moore's algorithm if the count is more than n/2 return candidate element otherwise return -1;

[@takeUforward]

The problem stated it will always have. Read the statement..

[@joeyaintwaffling]

@@takeUforward Oh sorry. Gfg has the same question and I was having this problem with your code that's why tried to help.

[@rohalkurup1350]

@@joeyaintwaffling Thanks , was stuck in this one when the freq is not greater than n/2 , So we just need to iterate again and check the occurrence of candidate element again Great

[@devanshmesson2777]

Thank you so much striver for making this series. It's very difficult to balance corporate life and youtube. Hats off to you brother!

[@sandeepnallala48]

bro never stop these videos : ) striver always Saviour to us : )...

[@RajSalla111]

You don't even need to mention the dislikes. that button is just invisible to thousands of learners. Thanks for taking us forward.

[@atharvakulkarni7141]

That was explained very well!!!

[@zeelthumar]

keep it my friend we are with you...

[@rohittakalkar9252]

Correction to the solution ( test case provided ) I think at the end, there is a need to scan once again to verify whether the majority element found using the algorithm is actually appearing more than n/2 times or not. Take an ex : 7,7,1,7,2,3 | 4,7 | 9,9,7,7 | 5,5,5,5 See here. The possible majority element found using the algorithm is 5. 5 may be the majority element, but it's not. So there is a need to scan once again to verify whether the possible majority element is actually a majority element or not Please let me know if I am wrong. I may be because I am not as experience as you 😇

[@takeUforward]

the problem states it will always have a majority element...

[@Plushvoyages]

there is no majority element in this case,as no element is occuring more thann n/2 times.

[@prakharagarwal4933]

Finally I was able to get the intuition I was been struggling ....

[@AbhishekGupta-xz1gd]

Work for example [1,1,4,3]. Here the majority is 1, but through this algorithm 3 will come as the output

[@abhisheksanwal1106]

No majority element exists in your example.

[@shouryasingh2193]

Pyara Explanation bhai 🤘👍

[@prasannapm3220]

thank you .Keep the good work going

[@sleepypanda7172]

more power to you. Loving your work

[@rryann088]

beautifully explained

[@ChethanaNP-jh2tr]

Great explanation!!

[@vishnuramj4660]

Dislikes don't stop u making videos keep on going. There are also guys who download your videos watch 10 times and didn't liked yet. If u consider this as a case i do like share and comment😁🥰. Waiting a next videos and all the series to complete. Your loving follower👽

[@arpanbhowmick847]

Thank you bhaiya Great explanation ❤️

[@naman_goyal]

Bro Ignore Unlike. you are making the best stuff for our placements .. tysm

[@awesomeps10]

how the heck is one supposed to come up with this algorithm in the real interview if you haven't read it beforehand....

[@anubhavgupta8164]

exactly

[@lovelymangal501]

That's why we do leetcode

[@sandeepnallala48]

impossible bro , even interviewers know that we go doing leetcode probs atleast

[@sjgghosh7677]

if we could come up with this kind of algorithm in such a short time span....this algorithm would be named after us XD

[@nidhish1407]

@@sjgghosh7677 Exactly 😂😂

[@vishnuramj4660]

Pls...Continue what u are doing now. One day really it will give some reward 💪

[@priyanshumahato5270]

dude you are doing such an amazing work always stay motivated

[@tannukumari5144]

great work bhaiya, thank you

[@mukeshjadhav1064]

Great hard work bhai and motivator too😍😍 really appreciated🔥🔥🔥

[@karandeeplamba8004]

Sound quality is awesome

[@amittiwari360]

In 2nd approach (using hash map ) why time complexity in worst case is O(n log n) and not O(n^2). because hashmap in worst case take O(n) and we are using one for loop so it should be O(n*n). Please help

[@ratankumar1399]

why this map based approach take TC 0(nlogn)?

[@aakashprajapati4836]

It was Nice video Explain very clearly ❤️❤️ Keep it up sir 👌🏻👌🏻