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.❤❤

[@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

[@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 ❤❤❤🎉

[@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

[@bhubeshsr6281]

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

[@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😊😊

[@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.

[@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..

[@346_PrachiRaut]

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

[@akashgite905]

tell them brute force then 🙂

[@vigneshkrishnan3766]

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

[@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.

[@anilkumar4200]

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

[@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!!!

[@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).

[@MaheshPatil-of1zy]

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

[@Surya1prakash]

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

[@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

[@Rohan-ce1sy]

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

[@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)

[@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]

[@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]

[@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

[@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

[@yasiromar5117]

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

[@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

[@rishabh1S]

Understood! Moore's Voting Algorithm is Awesome.

[@DevUpadhyay-q5i]

U r really great teacher of dsa...

[@cinime]

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

[@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 🔥.

[@habeeblaimusa4466]

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

[@rumiNITPatna]

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

[@DeepakPatel-d5v]

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

[@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

[@sarangkumarsingh7901]

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

[@supriyamanna715]

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

[@rickk3300]

Nice one 😂👌

[@waytoeterrnalpeace]

are amio bangali, striverer bhokto🤝🤝

[@anjalisharmav0307]

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

[@deepalivarshney23]

literally you are amazing .

[@shadowslayer2248]

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

[@Mrindia-k8n]

understood brother you are the best

[@mahakdashore8264]

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

[@aurobindsahu4355]

Understood &&&&&& Love from odisha bhaiya

[@musicalcasio5146]

huge respect for you no words 💖

[@shikhapatel6310]

int majorityElement(vector v) { // Write your code here int cnt=1; int ans; sort(v.begin(),v.end()); for(int i=0;i v.size()/2) { ans=v[i]; } } else{ cnt=1; } } return ans; } This can also be better approach

[@sajeethabegum4740]

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

[@vector9117]

understood , could we think of this approach without prior knowing meer moore whatever the algorithm is

[@Nithishkumar-bx9jf]

Understood! Really enjoyed your DSA lecture series ❤

[@saravna]

You dont have to loop through the array in the end to verify the count bro count++ and count-- => when this becomes 0 it ensures that total elements so for is 2n and when the final count is > 0 it ensures that the element with count !== 0 will have count > n/2

[@SinghDigna]

if array is must having a majority element then do this :- public int majorityElement(int[] nums) { int count = 0 , el = 0; for(int i = 0 ; i < nums.length ; i++){ if(count == 0){ el = nums[i]; count=0; } if(el == nums[i]){ count++; }else{ count--; } if(count > nums.length/2){ break; } } return el; }

[@infernogamer52]

Understood bhaiya ! Thanks a lot

[@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. ❤️❤️

[@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..!

[@_CodeLifeChronicles_]

oh my god the best course ever

[@Lakshya-f4l]

completed and understood!

[@berserker556]

Very well explained

[@merlingrace6850]

Thank you for such in-depth explanation and course❣

[@manan-543]

Understood. Your explanation is amazing.

[@KhannaPadala]

Understood bro, your explanation is top notch..

[@DevashishJose]

Understood, Thank for explaining it so beautifully.

[@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 ❤

[@padduchennamsetti6516]

understood very well,you are a gem

[@prathameshjadhav2942]

Thank you bro i got it

[@secretcoder7]

GREAT man on this earth

[@shubhamlipane8634]

Understood Thank You :-)

[@CodeQuest_28]

great explanation of moore voting algo..

[@sekharkumar3824]

Super Very well explained. Thank you

[@niharj5294]

i thought of an approach in each we sort the given array and return the element present at the index N/2 ..... this approach is taking O(nlogn) time and O(1) space complexity.

[@hari7939]

Just no words to thank you 🙏🙏🙏

[@lifehustlers164]

Completed 7/28!!!

[@pratikgupta7373]

wow really good and interactive lecture

[@shitalpashankar3117]

Love the way u teach, wonderful... thnks

[@ayushgupta0]

understood. I am going to make that interviewer happy.

[@theprogamer3924]

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

[@Code_eat_sleep]

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

[@radheshpandey4659]

@takeUforward, Bhayia this course is really awesome.💯

[@kingbadshah452]

thanks striver understood everything

[@kaichang8186]

understood, thanks for the great explanation

[@tholetigaargyreddy2613]

understood🥰🥰🥰🥰🥰best DSA videos everr

[@ShikharRaiyat]

I think the code could have been much simpler to understand if we would have wrote like this,just a suggestion :) int majorityElement(int arr[],int n) { int i=0; int cnt=0; for (int j = 0; j < n; j++) { if(arr[j]==arr[i]) cnt++; else cnt--; } if(cnt

[@dhruvrawatt9]

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

[@KrishnaSagar02]

Understood very well brother.

[@reki7247]

wonderful way of teaching!!! Understood!

[@shambhojaybhaye2822]

very good feeling confident

[@torishi82]

Amazing work. Respect!!

[@yashagarwal7042]

Very Great Explanation

[@mariselvamdheivasigamani578]

Understood. Awesome explanation

[@poojarai3528]

Thanks for your support❤

[@Engineer-fo1dl]

Understood Clearly ❤

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@shesparks64]

Thanks for making concept soo simple to understand :)

[@ishasinghal3457]

Best explanation ever❤❤

[@vedanshagrawal3918]

Beautiful algorithm, need to be on quality crack to come up with this in an interview.

[@samuelfrank1369]

Understood. Thanks a lot . Please make more videos

[@aryan6470]

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

[@shashankshekharshukla5743]

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

[@Hipfire786]

understood everything sir awesome video

[@konankikeerthi]

Understood bro. Thank you for your efforts

[@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).

[@sulabhnapit5042]

sort the array and simply return a[n/2] element always true

[@aastikofficial6100]

understood 🚀