Majority Element I | Brute-Better-Optimal | Moore's Voting Algorithm | Intuition 🔥|Brute to Optimal

[@takeUforward]

Please watch our new video on the same topic: kzbin.info/www/bejne/rKi9m2SBZcpsi5o

[@suchitakulkarni2744]

Bhai have a doubt .. after the loop if we check cnt is not equal to 0 and return el then also the program executes properly then why we are again taking second loop ..?

[@pallavi22222]

@@suchitakulkarni2744 The first loop will only give you the majority element, the second loop is used to check whether the frequency of the element from the first loop is greater than n/2. You can clearly understand this by watching once again the video from 13.00 where raj bhai explains by changing the last 4 elements to 1.

[@ShreyasinghIITPATNA]

int majorityElement(vector v) { int n=v.size(); sort(v.begin(),v.end()); return v[n/2]; } this is also accepted and time complexity is O(nlogn) space is O(1)

[@aadeshkumar819]

@@suchitakulkarni2744 if the problem statement says that there will always be a majority element then you don't need the second loop but if it doesn't guarantees a majority element then you have to check. timestamp : 17.00 . hope this clears

[@ammankhan3370]

@@ShreyasinghIITPATNA how? whats the last line return v[n/2];

[@factsmadeiteasy9943]

No matters how hard the paid courses gang will try to defame you or stop you , we STUDENTS will never stop promoting you among our friends and support you in your journey.❤❤

[@346_PrachiRaut]

"sitting in an interview u cannot invent the algorithm" LMAOOOO xd

[@akashgite905]

tell them brute force then 🙂

[@krunalkp1032]

That's true how the hell someone can come up with this algorithm with their own , unless he is really well versed in math

[@anilkumar4200]

Thanks for lectures from bottom of my heart.Keep doing good work.

[@takeUforward]

Let's march ahead, and create an unmatchable DSA course! ❤ Use the problem links in the description.

[@harshavardhan184]

Hatsoff to this consistency

[@CodeBoost8375]

Time Stamp 0:43 - Problem Statement 1:45 - Brute Force Solution 2:58 - Better Solution 4:46 - Code (Better Solution) 6:58 - Optimal (Moore's Voting Algorithm) 7:38 - Dry run + Intuition 14:37 - Code 16:52 - Time complexity 17:36 - Outro

[@umakantbhosale4718]

Hey Striver bro , It will be humble request from myside that could you please explain the approaches in Hindi&English language if possible. It will be very useful for many of students like me.

[@utsavseth6573]

You dont have to ask for likes RAJ. You will get them even if you dont say. THis level of top notch content will not go un-noticed.

[@DeepakLalchandaniProfile]

Wow hats off ❤❤❤🎉

[@aamirarshad4536]

one leetcode a day keeps unemployment away

[@shubhamkumar-hx1fb]

Bro... don't ever say this 🤐

[@jaswanthreddy7135]

Really?

[@barnam_das]

wah arshad wah

[@utkarshrai101cartoonwala]

Reality is often disappointing.

[@rishabhranjan5162]

not even the bare minimum to get a job bro

[@bhubeshsr6281]

Striver Bhai Level of Dedication and hardwork u put on this is .....

[@lisachakraborty528]

u make me fall in love with coding there was a tym i hated it i started late but yes you are true inspiration

[@NeelakshiSachdeva]

I'm hating it now. Not able to build intuition myself. Always dependent on video solutions. Sometimes I feel I'm too dumb and not built for this thing. What should I do 😭😭

[@lofi_world_4.7]

@@NeelakshiSachdeva uss bro uss

[@geotalesalltime]

@@NeelakshiSachdeva don't give up ! are you still practicing now

[@NeelakshiSachdeva]

@@geotalesalltime yes I got back again 🥺

[@geotalesalltime]

@NeelakshiSachdeva carry on, 4th yr placement season is going on, very tough situation 💀🥲

[@anizmo]

Great explanation of Moore's Voting Algo, very intuitive. Intuition: when there is a majority element its count will not be cancelled out.

[@impalash_ag]

Hi Raj, Thanks for the video. As per your explanation, one more slight optimisation we can do in Moore's Voting Algorithm if we're not sure whether majority element exists. Say we have array size n and n%2==0(means and even size array) and if our count value at last is also 0 in that case we do not need to go to the 2nd step i.e. traverse the whole array again to get the occurrence of element(ele variable value). Hope it makes sense.

[@ParasSharma-mf8or]

0:00 Introduction of course 0:46 Majority Element(>n/2) 1:48 Brute approach 2:17 Pseudo code (Brute) 2:56 Better solution 4:45 Code-compiler (Better solution) 6:59 Optimal(Moore's Voting Algorithm) 7:56 Algorithm explanation+Dry run 14:37 Code-compiler (Optimal approach)

[@Surya1prakash]

Understood! Bhai never gone through such type of explanation ....thank you very much....

[@Mrindia-k8n]

00:04 The problem is to find the majority element in an array, which appears more than n/2 times. 02:08 Implementing the Brute Force solution and understanding its time complexity 04:12 Iterate in the map to find the element occurring more than n/2 times 06:17 The Moore's Voting Algorithm is an optimal algorithm to find the majority element in an array. 08:22 The majority element in an array can be determined using Moore's Voting Algorithm. 10:37 The majority element in the given array is 5. 12:51 The majority element is determined using Moore's Voting Algorithm. 15:04 Implement Brute-Better-Optimal algorithm using Moore's Voting Algorithm to find the majority element. 17:12 The time complexity of the most optimal solution is O(n) and the space complexity is O(1).

[@ArcGaming07YT]

Let me help u guys understand : point 1 : moores law gives ans when there is strictly majority element present in the array. point 2 : use this example to understand it in clear way [1,2,1,3,1,4,1,5,1] if last last number was not 1 then it clearly means that there is no majority element in array else its 100% that it will be the last element in above example point 3 : understand it more by seeing these examples [1,2,3,4] gives ans as 4 but its not valid array as (there is no majority element in it) point 4 : there is no chance that we will get any other number other than majority number as ans,if there is strictly majority number present in the array and if the array is not only the valid array i,e(there is no majority element in it) then ans can be any value.

[@ahtesham4003]

👏👏

[@anmolprasad6813]

Thanks bro, I was so confused on this point (We could get 1 as the ans despite it not being majority) but your comment cleared it

[@AffairWithGeo]

So this is valid if there is strictly a majority, else not possible? [2 2 2 1 1 1 3 3] as per the video logic 3 comes as majority. But N/2 = 8/2 = 4 to be an answer, answer has to satisfy, answer > 4. So seems like no way to . . . .??? Plz help to make things clear

[@aryanpinto5105]

@@AffairWithGeo The question does mention that there does exist a majority element. Your test case itself is invalid becoz it doesn't have any majority element.

[@lucy2003-d8p]

i dont know why but you really helped me😊😊

[@ashishbm3565]

very great intutions bhaiyaa!!! you are a legend. never thought i would be enjoying dsa and leetcode like this... i dont care i get a job or not but i have to finish this just for the thrill!!!

[@shubhamagarwal1434]

#Free Education For All.. # Bhishma Pitamah of DSA...You could have earned in lacs by putting it as paid couses on udamey or any other elaerning portals, but you decided to make it free...it requires a greate sacrifice and a feeling of giving back to community, there might be very few peope in world who does this...."विद्या का दान ही सर्वोत्तम दान होता है" Hats Off to you man, Salute from 10+ yrs exp guy from BLR, India..

[@CodeBoost8375]

Understood! Very well.None of them can match your dedication and energy.🔥🔥🔥🔥 And when you explain how algorithm is working the first thing comes in my mind damm! Yarr ye to kisi ne bataya hi nahi tha how the cnt is working.

[@manipandit18]

Understood !!! Time Stamp 0:43 - Problem Statement 1:45 - Brute Force Solution 2:58 - Better Solution 4:46 - Code (Better Solution) 6:58 - Optimal ( Moore's Voting Algorithm ) 7:38 - Dry run + Intuition 14:37 - Code 16:52 - Time complexity 17:36 - Outro

[@Rohan-ce1sy]

Very good explanation. Better than any paid DSA course in market. Thank you so much Striver bhai.

[@MaheshPatil-of1zy]

Seating in Interview you cant discover this algorithm🤣🤣🤣🤣🤣

[@cinime]

Understood! Super fantastic explanation as always, thank you so much for your effort!!

[@amanpreetsinghbawa1600]

Striver just when you mentioned about the keeping the count & element variable, I almost solved it that moment. Thanks for building up that intuition skills, it's been 2 months since I have been practicing via ur playlist🔥

[@yasiromar5117]

Loved the way you explained brother. You're a true magic man

[@supriyamanna715]

Buk e amar gorom rokto, amra striver er vokto! great content!

[@rickk3300]

Nice one 😂👌

[@waytoeterrnalpeace]

are amio bangali, striverer bhokto🤝🤝

[@vigneshkrishnan3766]

you can use this solution too........ sort(a.begin(),a.end()); int mid=a.size()/2; return a[mid];

[@theprogamer3924]

nicely explained. even though I slept while watching the video, I woke up again and understood the solution xD thanks

[@Manishgupta200]

Super Duper Amazing... Your explaination from brute-better-optimal is fantastic with Time and Space complexity. Moor's Voting Algorithm explained by you is really awesome without using any extra space. The best thing like once in a blue moon type.. I liked the most is you explain in a unique way in every tutorial.. Here is.. like.. How Time complexity is O(N) not added (because in problem, array have atleast one majority element. So, here TC < O(N) always at the time of checking majority) in Moore's Voting algorithm at the time of checking 'el' is majourity or not.. And also you explain Space Complexity also. Thankyou Striver for such an amazing tutorial 🔥.

[@DevUpadhyay-q5i]

U r really great teacher of dsa...

[@mahakdashore8264]

what a WONDERFULL EXPLANATION sir,understood every thing,please keep making these kinds of videos for us sir, please

[@sarangkumarsingh7901]

Understood Sir.............Awesome lec.......

[@rishabh1S]

Understood! Moore's Voting Algorithm is Awesome.

[@aurobindsahu4355]

Understood &&&&&& Love from odisha bhaiya

[@DeepakPatel-d5v]

Thank You Striver Bhaiya for Such a Quality Content...

[@habeeblaimusa4466]

Consistency 🔥 🔥. Thanks for all you do. I really appreciate

[@shadowslayer2248]

Understood and practiced the code as always! Let's really Take Ourselves Forward!!

[@shubhamjoshi8117]

@takeUForward , awesome explanation, really appreciate your efforts. The way you explain stuff is really remarkable. I see a small bug in the code class Solution: def majorityElement(self, nums: List[int]) -> int: ele = None count = 0 for num in nums: if count == 0: ele = num # count += 1

[@sajeethabegum4740]

Very good explanation. Easy to understand. Thanks for posting this video. Hats off to your dedication.

[@ayushgupta0]

understood. I am going to make that interviewer happy.

[@rumiNITPatna]

thanku so much striver! i started loving dsa because of u

[@hectorf44]

Thanks!

[@JAY-bq4kw]

class Solution { public: int majorityElement(vector& nums) { sort(nums.begin(),nums.end()); return nums[nums.size()/2]; } };

[@calisthenics5247]

Try your code for [1, 1,2,2]

[@_CodeLifeChronicles_]

oh my god the best course ever

[@anjalisharmav0307]

just a quick reminder for you bhaiya: thank you for making the course!

[@KhannaPadala]

Understood bro, your explanation is top notch..

[@deepalivarshney23]

literally you are amazing .

[@vivekreddymynampati6996]

class Solution { public: int majorityElement(vector& nums) { int n=nums.size(); sort(nums.begin(),nums.end()); return nums[n/2]; } };

[@calisthenics5247]

Try your code for [1, 1,2,2]

[@WabiSabiThereader]

Thank you sir you are a blessing to us students

[@dixitnakhva6181]

2 things: 1) this algo will give you majority element but it can be true for only last some portion of array(i.e 2 3 2 3 1 algo will give you 1 but it's only true for last portion of array which [1] and it's of size 1 but it's not true for whole array) , now comes to 2nd step 2) algo give you probable majority element, now check whether it's correct or not by iterating over an array In case of 2 3 2 3 1 Algo gives you 1 as probable majority element Now, by applying 2nd you will find out that 1 is not majority element if we consider whole array of size 5 So, it means array doesn't have any majority element Because if it does, it would have caught by algo But the probable majority element that algo gives us (1) is also not an answer, so there is no majority element in an array

[@rakeshnagarkar8759]

I stuck with the algorithm thinking that it only works with last portion of array to find majority element but your excellent explanation removed my confusion, thank you.

[@dixitnakhva6181]

@@rakeshnagarkar8759 you're welcome dear

[@DevashishJose]

Understood, Thank for explaining it so beautifully.

[@dhruvrawatt9]

Looking forward more such videos from you bhaiya , you are awesome.

[@MAX_RITIK]

i just watch the video ,understand the concept but doesn"t code right away i try to solve the same question on leetcode after 1-2 days .this relly help me to use my own mind while code . and amazing job striver for making coding simpler

[@Nithishkumar-bx9jf]

Understood! Really enjoyed your DSA lecture series ❤

[@manan-543]

Understood. Your explanation is amazing.

[@syedtahaseen4468]

06:48 All elements in the array are not unique though. There will be an element of size N/2+1 so in worst case the sc will be O(N/2+1). But yeah we will take it O(N/2+1) ~ O(N).

[@Code_eat_sleep]

Understood . Thank you so much bhaiya for such a clear explanation.

[@padduchennamsetti6516]

understood very well,you are a gem

[@tholetigaargyreddy2613]

understood🥰🥰🥰🥰🥰best DSA videos everr

[@himadriroy7980]

Oh God dimag hil Gaya pura. How did someone invent so innovative algorithms and how can someone explain it so lucidly. Striver daa you are just CODING GOD. Uff 🔥🔥🔥. May God bless you always. ❤️❤️

[@merlingrace6850]

Thank you for such in-depth explanation and course❣

[@secretcoder7]

GREAT man on this earth

[@infernogamer52]

Understood bhaiya ! Thanks a lot

[@pratikgupta7373]

wow really good and interactive lecture

[@Mrindia-k8n]

understood brother you are the best

[@shitalpashankar3117]

Love the way u teach, wonderful... thnks

[@sekharkumar3824]

Super Very well explained. Thank you

[@reki7247]

wonderful way of teaching!!! Understood!

[@torishi82]

Amazing work. Respect!!

[@shesparks64]

Thanks for making concept soo simple to understand :)

[@riyadhossain1706]

I really appreciate your hard work, bhaiya. Love from the core of my heart from Bangladesh 💝💝

[@radheshpandey4659]

@takeUforward, Bhayia this course is really awesome.💯

[@RamKumar-dm6es]

"Sitting in interview , You can't invent this algorithm" funny line. And Understood

[@mariselvamdheivasigamani578]

Understood. Awesome explanation

[@shyam.upadhyay]

Awesome content bro, love you!

[@anuragbhardwaj13]

While solving the problem I wrote my own solution, it's O(nlogn) because we need to sort the array but it's passing all testcases and even time complexity test : just have a look at it : static int majorityElement(int a[], int size) { // your code here //sorting array here will take O(nlogn) Arrays.sort(a); int count=0; //traversing array once O(n) for(int i=0;i0&&a[i]>a[i-1]){ count=0; } //else increasing count count++; //checking majority if(count>size/2){ return a[i]; } } return -1; }

[@AdityaKumar-be7hx]

If you sort the array then the answer is simply the element at n/2 index it the sorted array. Nothing to do after sorting

[@firstacc5442]

@@AdityaKumar-be7hx 😂😂😅

[@m_fi8926]

ohhh

[@konankikeerthi]

Understood bro. Thank you for your efforts

[@hari7939]

Just no words to thank you 🙏🙏🙏

[@ishasinghal3457]

Best explanation ever❤❤

[@zskhan7496]

Hamara driver top gear me gaadi chala raha hai 🔥🔥🔥😁

[@CodeQuest_28]

great explanation of moore voting algo..

[@aryan6470]

Pta ni comment ap tak pahuchega ki ni bt this means alot t us which i can describe in the words ❤

[@SaiPrakashJ-c9m]

Understood👍 Thank you so much

[@kaichang8186]

understood, thanks for the great explanation

[@shubha_jagadeesh]

as always , well understood 💌

[@desiquant]

I don't think you need to loop over the map to find the majority element. You can add an if statement next to where you update the frequency of the map as following: freqMap[nums[i]]++; if (freqMap[nums[i]] > nums.size() / 2 ) { res = nums[i]; break; }

[@Future_software_enginneer]

Done .. Concept clear but want to do revise ❤😊 pls like so it remind me to watch again for revision thankyou bhaiyaa love uh ❤

[@twinklelight9829]

thankyou striver!!!! we appreciate your work☺☺

[@Hipfire786]

understood everything sir awesome video

[@Sachinkumar-ou5vu]

#bhai shab what an amazing explanation

[@as_if]

12:40 the count has no significance but if the count=0, then there shouldn't be any majority element. That's what it's significance is. Right?

[@shreyaschauhan229]

Thank you sir for this.

[@berserker556]

Very well explained

[@samuelfrank1369]

Understood. Thanks a lot . Please make more videos

[@vanshjais1777]

huge respect for you no words 💖

[@shyam.upadhyay]

In the optmal solution, we can directly return the element there is no need for another for loop. And in case it doesn't exist then, we can just check if the count is 0 or not and return the ele or -1.

[@Srinivasssssss]

But it will not work when the input array having odd length..!

[@sunilkamat8199]

Superb Explanation 😍

[@KrishnaSagar02]

Understood very well brother.

[@shashankshekharshukla5743]

Thankyou bhaiya may God bless you always. Love you 💗 striver

[@Engineer-fo1dl]

Understood Clearly ❤

[@KunalSENPAI]

Awesome explanation as always!!

[@shubhamlipane8634]

Understood Thank You :-)