hey if you're welcome back to the channel I hope you guys are doing extremely well so this is another video from the Strivers A to Z DSA course just in case you're for the first time here this is world's most in-depth course in DS algo why do I see that this cost us 456 modules by the end of the post you would have sold more than 400 plus problems in DS algo and you can go across the entire internet you can buy any of the paid courses none of them will be covering DS algo in such step so one thing that I can assure you is once you complete the entire post you can actually clear any of the DS algorithms in any of the companies in any part of the world so till now we have covered uh dell certain arrays of certain array of zeros ones and twos and in this video I'll be covering majority element so what does the problem majority element States it states that you'll be given an array of integers now your task is to find me the element that appears more than n by two times very important lining more than n by 2 not equal to two it has to be more than n by 2. Imagine n is eight then it should appear more than four times imagine n is 9 in that case 9 by 2 will take the floor value it is four so it should appear more than four times got it so in this array if I ask you which is the majority element how many like what's the length of the array three four five six seven seven is the length of the array can I say two appears for four times which is greater than n by 2 so 4 over here is your answer and this is what you have to tell me given an array tell me the element that appears more than n by 2 times so what will be the Brute Force solution to this particular problem it's going to be very simple I'll pick up an element and then I'll scan through the entire array basically do a searching through the entire array and I'll count plus plus and if at the end of the day the count appears to be greater than n by 2 for any of the element that is my answer first I'll pick up two next I'll pick up two next I'll pick up 3 and scan through the entire array next I'll pick up 3 and scan through the entire array this is what the Brute Force solution will be and the code will look something like this so it's very simple you just iterate through the entire array for the first time pick up two and scan through the entire array and keep a check and count after you have scanned through the entire array by taking array of I you check it the count is greater than n by 2 if it is then you return array of I and forward like out of the for Loop you can return -1 just in case there is no majority element so this is how the Brute Force solution will look like what will be the time complexity obviously we are using couple of Loops so it is we go of n square and when you give the solution to the interviewer the interviewer will not be happy and will ask you to optimize it this is when you'll be giving the better solution so what will be the better solution The Brute is taking n Square so we know one thing for sure the better solution will be somewhere of the order n log n or B go of n or 2N but it is definitely going to be better than n n Square so if I have to think what are we actually doing we are counting we are counting and we're looking for which element appears more than n by two times so yes yes we can use hashing it's very simple if there is a count we have to keep a track of how many times a Dockers the only technique that comes up to my mind is hashing that is what I will be doing so what I'll do is I will declare a hashma with the element and the count where the element is my key and the count is my value so this will be the representation in the map for a clear n value now what I'll do is I'll be like let's scan through the array it is two so I'll put that 2 and I'll probably tell him you okay once then I'll move and then I'll say you okay twice then I'll move and there's a three I'll say a doctors once then I'll move and there's a three it occurs twice then I'll move one occurs once then I'll move two occurs twice then I'll move two occurs four times so once you have completed the entire iteration now it's time to iterate in the map yes it's time to iterate in the map so if I iterate in the map you will see that this particular Guy 2 occurs four times which is greater than n by 2 which is three so two is your answer so just I trade in the map and see which element is occurring more than n by two times so let's quickly quote the better solution of the problem link will be in the description so we need a map to keep the count cell declare a map okay what is the next thing we have to iterate so let's quickly iterate and now once am I trading I'll say ma what's the element vfi do a plus plus so with this iteration I will be marking it in the map now what is the next job I trading the map and see which is more than n by two times so this is how you iterate in the map in C plus plus the Java port and the python code is in the description and now you say ID dot second because that is the value is greater than are you greater than V Dot size Y2 if you are then near the majority element and you know the key is very simple it's at the first place so the key will be the first place if after this there was no one you can simply say return -1 and now we will quickly go and run this off and see if it is running fine okay looks like it is not why is it not tap was not declared let's quickly go and declare hashing clue everything is running absolutely fine now it's over the time complexity can I say the first Loop is running for bego of N and there's a ordered map used which is which is going to take logarithmic of n if you use something like unordered map then this logarithmic of n will go off only in case of average and best case in case of worst case another map ends up taking the ego of end time within itself so that is an N login and what is how many elements are there in the map imagine you're given an array something like this then each of these elements will be in the map so thereby the worst case the map might end up taking n so what is the total time complexity can I say it as we go of n log n again depending on which map you're using and a big go of N2 Traverse in the map ever the space complexity we go of n because you are storing all the elements in a map data structure so this will only happen if the array contains all unique elements remember this so the moment you give this hashing solution to the interview he'll be like hey wait you are using an additional space complexity can you please optimize this that's when you'll be talking about the most optimal algorithm and that will be using something as the Moose voting algorithm now sitting in an interview you cannot invent this algorithm so you have to know this algorithm beforehand so you might be thinking but does that mean we have to mark it up no the interviewer will be grilling you on thought process and intuition if you mug up the algorithm and you just present it line by line you'll understand that you have marked up the algorithm so please make sure you understand the thought process intuition and the algorithm in depth so please make sure you watch the video till the end because you're going to take away a lot of things when the video ends so how will I be explaining this particular algorithm what I'll do is I'll do a Dryden of the algorithm and during The Dryden I'll be sharing the thought process and the intuition behind every step that this algorithm does so that it sticks to your mind okay so what is the algorithm all about it's very simple it's about two variables element and Dot initially count is zero and you can say initially the element is not initialized and we start iterating so whenever we are iterating and we are the first element or whatever if the count is zero that means we haven't taken any array please hear this out properly we still haven't taken any array so you will be like okay I will take seven and I'll increase the count to 1. so what I did was I said I will consider this 7 to be my answer I'm just taking a hypothetical assumption that 7 is my answer and the Countess one and now let's start moving we again move to seven like seven now this occurs twice five no it is not seven so you reduce the count remember this count is not storing how many times seven appears it doesn't have some other significance which I'll say next again seven increase next again five degrees next one degrees so whenever you find 7 you increase because 7 was your element whenever you find anything apart from Seven you decrease now you are reaching zero until how much till this portion let's understand what so if you take seven seven five seven five one this is an array rather this is an array and the count over here is zero what does the count signify so you took the element seven how many times does it appear three times how many times the author elements appears where other includes five and one the other element appears three times this is the reason when there was a seven you did a plus plus so there were three plus plus done and when there was five five one there was a minus minus minus 10. so 3 plus 3 minus ended up giving you a count of zero can I say something for sure if I just consider this array just consider this array 7 is definitely not my major retirement why if seven was my majority element how can you cancel because for if an element appears more than n by two times there is only one limit which appears more than n by two times and you cannot cancel it all if there are six elements and seven appears four times can you cancel four to cancel 4 you need four more so it's not possible since 7 appeared three times in a six length array which is not greater than n by 2 it is equal to equal to n by 2 so it got canceled so something that I can assurely say is till here 7 is not my majority element till here it's not so this cannot be considered as an answer but what I will do is I'll move ahead and I'll move to 5 okay the moment I move to 5 I find count is zero so what I'll do is I will just quickly say okay listen count is 0 so can you please take this as my new majority element and probably I'll start checking from here and my count will be one perfect so I will take five I'll make the count one let's move seven it's not equivalent so I'll just make it zero I just make it back zero so this time the array finishes here and the count becomes zero again eminent if I just take this particular array can 5 be the majority no that's why next we'll move ahead the moment we move ahead what will happen since count is 0 it will again initialize count to 1 and element to be five and we will start the array again from here and this time again let's move it's five increment it is seven decrement it is seven decrement so can I see in this particular array what happened five five seven seven what I can say is hey 5 was occurring twice seven hours occurring twice so it brought cancer thereby count was Zero thereby 5 also cannot be my answer so till now whoever I have considered as a majority got canceled by similar elements so till now no one has dominated we are still looking for someone who is dominating got it everyone has still no cancer let's go ahead what is the count value Crown's value is zero now so let's move it we are at account zero so again we start the count will again become one and this element still stays as five this time we'll move ahead count becomes 2 7 will move out count becomes three this term will move ahead count becomes four and we can say we have ended the iteration we have ended the iteration so since we have ended the iteration there is an element five this count has no significance but we have an element five this element 5 will be your maturity element if there exists a majority element why because everyone else got canceled off within itself so if there is someone still remaining who did not got canceled then that is my answer but am I sure that element 5 is the majority element what I said if there exists a majority limit it will be five and no one else if if there is a majority element it will be five and no one else if there doesn't then okay fine for example if the last portion was something like one one one in that case you'd have bought one and the count would have been four but is one the majority element if you see one just appears four times maybe five that's it one app is five times and when you look at the length of the array it is six two four and four which is eight plus four twelve it's a 16 length array someone has to appear more than eight times to be majority and since it is five let's see 5 is so let's see how many times five is once twice twice four five six seven eight nine five appears nine times out of which four times when not canceled four times when not canceled but the other times it was canceled so the other five times zeros canceled got it so I can say five is my major element it's a very simple process the first process is to apply moose voting algo okay about the second process verify if the element that you got the element that you got is the majority or not how do you do it whatever the element is in this case the element was 5 just iterate through the array again and see how many times 5 appears this time it will come out to be 9 which is greater than the length 16 by 2. so that's why the 5 is if it doesn't then it is not got it so I hope you've understood the intuition it's very simple if someone appears more than n by two times it will not get canceled quite simple right that's the intuition so coming back to the code editor again the problem link will be in the description so what do we need we need account zero and we can keep an element normally now let's quickly start off with zero and probably V Dot size yes and how can I say first thing that I will check is what if the count is 0. if the count is 0 I know for sure this is where I'm starting a check for a new section so ground will be one and the element will be V of I right but what if the count is not zero in that case I will check if V of I is equal to equal to the element that I was thinking it's it's the majority if it is please increase if it is not okay let's reduce simple three lines if the count is zero we just assign and we move I plus plus if it is equal equivalent we just increase count and we move if it is not then we decrease and then we move so what will happen is when you're decreasing if the curve becomes 0 when you increase and when you come back the count will be checked with 0 and it will be replaced with the newer limit and it will start a new section quite simple and once you've got the element just iterate over here and V Dot size all right plus plus and you say Hey listen if V of I is equivalent to element probably you can keep something like counter one equal to zero and you can say counter one plus plus if at the end of the day counter one is greater than V Dot size by 2 again you can store B dot size in some variable this particular element is the answer or else you can say the answer is minus one or whatever they are asking you to return so what I'll do is now I'll quickly go and run this off and see if it is running fine no it does or it'll be counter one plus plus counter one done and let's quickly submit this off I hope it does run now remember one thing whatever is the value of counter at the end it doesn't represents anything so we have to talk about the time complexity how much a single Loop and three Fields so it's a single Loop so whenever it's a single Loop you know the time complexity is very simple it's we go off n for the burst iteration of the most voting algo and if they are stating that the the array might have or might not have a majority limit then you go and verify this step will not be done if the problem states that their own ways exist a majority element then this step will never be done okay you only do the step if the prop if the array might not have a majority element got it so this will be the time complexity and we are not using any extra space so this will be the space complexity of the most optimal solution coming back to the sheet I can say that this particular problem is done and if you understood everything please please do with that like button is just one like it won't cost you anything please do consider hitting that like button and look at your tradition do comment understood so that I understand that you understanding everything and if you're new to our Channel please please do consider subscribing to us because it's like 1 23 am in the morning and after my office hours I'm recording this video so if you if you consider subscribing to me that will motivate me to make such more videos is broken don't ever forget you're golden I will find