Hi, everyone.
So in this video, we are going to solve this question, find the majority element inside the.
OK, so what is the majority element?
So element is to be a majority element if it appears more than and by two times, OK.
What is and and is basically the size of the area.
OK.
And is basically the size of the area.
So if there is an element, if there is an element that appears more then and by two times OK, so more
then and by two times then that element will be called as majority element.
OK, let's take some example to understand the question.
OK, so in this case, the value of N is basically three.
OK, size of that is basically three and we can see the majority element.
OK.
In this case, the majority element is basically three.
You can see three is appearing two times, three is appearing two times.
And what is and by two so and by two is basically three by two which is basically one OK.
And two is basically greater than one.
So greater then and by two OK.
So in this case our majority element is three.
OK, so we have to return three.
We have to find the majority element and we have to return the majority element.
Let us consider this example.
So what is the value of N?
So the value of N is basically one, two, three, four, five, six and seven.
So the value of end is basically seven.
What is and by doing so and by two is basically three.
Now see in this case the majority element is basically two.
So the majority element is basically two and two is appearing basically four times.
Two is appearing in the area four times and four is basically greater than three.
Four is good, then three.
Now, let us consider this example.
Let us try to find out the value of end first.
So the value of N is basically one, two, three, four, five, six, seven, eight, nine and ten.
OK, so the value of this basically ten letters and by two, so end by two is basically five.
Now count the occurrence of four.
So one, two, three, four, five and six.
So basically in this case, my majority element is four because it is appearing six times and six is
basically greater than five then and by the majority element is that element that will appear more than.
And by two times now, let us consider this example.
So in this example, the value of N is basically five nowadays and by two so and by two is basically
two.
In this case, majority element is not there.
So in this case.
Majority element does not present a majority element is not present, but.
We can assume that the majority element is always present.
Now see the question.
So this is basically a precaution.
Again, majority element.
And the question is, we can always assume that basically the majority element will always exist in
there.
We can assume that the majority element will always exist.
So that means we will not receive input like this.
We will not receive input like this.
So we can safely assume that the majority element will always be there.
We can assume that the majority element will always be there and input like this will not be there and
put like this will not be there.
Now, let us try to solve this question.
So let's discuss various approaches of solving this question.
Now, first, let us discuss the very simple approach, the brute force approach.
So what is the new approach?
So naive approach.
What it will say.
So you have a Netty and you have elements.
So what is the new approach?
And I will say find the occurrence of this element.
So what I will do, I will pick this element.
I will pick this element and I will find its occurrence by iterating over that completely.
Now, I will check this element and now I will find the occurrence of this element or the completely
similarly pick the third element and find a talkathons.
So brute force is very simple, but we have to do I will pick one element and I will try to find it
over the complete area.
If I'm able to find an element, if I am able to find an element whose occurrence is basically guerdon
and Bitel, I will return that element.
I will return that element.
So what be the time complexity so complex?
It is very simple.
We are picking each and every element and I will try to find the occurrence of that element.
So time complexity is basically and square and the space complexity is basically big often.
So this is the brute force approach.
Now, one more thing, since what is the majority element?
So majority element is that element whose occurrence is basically guerdon end by two.
So that means we can have only one element as the majority element.
OK, so there will be only one majority element.
We cannot have more than one majority element because their definition of majority element is basically
that element whose occurrence is greater than ENVI two.
So they will be always one element that will be the majority element.
Now, let us discuss the second approach.
So in second approach, what we can do, we can take the help of Hashmat, we can take the help of map.
So what we will do, so we will store element and we restore its count, give a loopier.
OK, so this will be my key element.
And so what will happen?
So this will be my area.
But I will also I will iterate over the area and I will fill this hash map.
I will fill the hash map, so after reading over the completely, my hash map will be ready now.
It will do so.
Let us take an example.
Look.
So let us take a small example.
Let's say this is my example, three to three.
OK, now let us make of it.
Let us say it so after trading threes, basically a beating two times and two is basically a beating
when times.
OK, so this would be my shrimp.
Now, what I will do with the hash map is ready.
We will address or the hash map.
And when we are dealing with the Hashmat, we can check.
So if there is an element whose occurrence is basically good and by two, if there is an element, we
will return the key.
OK, the whiskey.
So I will return the key.
OK, very, very simple.
So what will be the time and the space complexities or the time complexity.
We are just iterating over the array and then we will try to add hash episode time.
Complexity is big often and the space complexity is also big often because we are using hash map.
OK, so space complexity will be big often.
Now you can also see the space complex.
It is big off and too, because we can say the majority element, we can always assume that the majority
element will always be there as given the question.
So basically the size of the Hashmat will basically be.
And by doing it, by doing basically nothing.
It is just big often.
OK, so I will say.
The space, complexity and that complexity, both are linear.
OK, now let's discuss the third approach.
So what is the third approach?
So in third approach, this is basically called the starting approach.
So what we will do in sorting so let's say this is really what we will do.
We will basically start daddy, OK?
So after sorting the idea, what will happen?
So after sorting the idea, what will be my majority element?
OK, so what is the majority element?
Majority element is that element which is all and vital times.
So after sorting the area, I will find out the main element.
This is my element.
So what is is basically and vital and this will be my majority element.
OK, so what I have to do, I have to do two steps.
So first step is basically start the.
First step is very simple, we just have to start the.
And since the majority element is that element, which is appearing more then and two times so the size
of the area is basically then we will find out the main element.
And that element is basically the majority element.
OK, very simple.
So what would be the time complexity since we are using starting small time complexities and log-in
and then we can find out the in question time and then we can return them.
And the space, it is basically big often.
So this is the third approach starting now, let let's discuss the best approach.
OK, let's discuss the best approach.
So this is approach four, and this is basically called voting approach.
More swotting approach.
OK, Moray's wording approach.
So this is the best approach now where this approach will do so.
What is the best?
First, discuss the intuition.
OK, now there exists a majority element.
OK, so we know majority element exists.
So what is the majority element?
The majority element is that element which will appear more than two times, OK.
And these are sort of the elements of elements.
So what I will do, so I will mark the majority element.
So I'm discussing the inclusion, so I will mark the majority element plus one.
OK, if there's a majority element, that means I will market my platform and that's all the elements
will be marked as minus one sentence majority element of and by two.
So if you will add these two plus and minus one, finally your output will be plus one, not necessary
plus one.
Basically it can be positive.
OK, it can be anything plus two plus three plus four.
Anything but the output will be positive, very positive because the majority elements, they are appearing
then and vital times and the rest of the elements are basically Leiston and by two times.
So I am making the majority element s plus one, and that's two of the elements on Minocin.
So if you will add the majority element with the rest of the elements.
The output will be a positive element.
OK, so this is the indication now let let's discuss the approach.
So the approach is very simple, but what more voting algorithms is so consider you have elementally.
You have elements, and I am saying this element is basically a majority element element, the majority
element.
So what do we do if we will cancel out each occurrence of element, each with other elements that are
different from each?
Then it will exist until the end if it is a majority element.
OK, I am repeating myself.
The approach is very simple.
It is it will use the endurance or element.
It is basically a majority element.
OK, I'm saying I am assuming element is majority element.
Now if I will cancel out all the elements or these are all of elements.
So if you will cancel, if you will do it, which is the majority element, minus all the other elements.
E minus all of their elements.
So what will happen?
So basically it will exist till the end.
It will exist till the end of time.
Doing so if I will cancel out each occurrence of an element e from the all other elements that are different
from E, then it will exist till the end if it is the majority element.
OK, very simple approach.
Let us take an example to understand it.
We will take few example and then we will write the code.
So let us take this example three to three.
Three to three.
So initially, I don't know what is the majority element, so let us assume something, let's see.
My candidate of the majority element is the first element three and obviously each count is basically
one.
OK, so what we have to do, if I will encounter a different element, I will subtract, I'm assuming
my candidate for the majority element history.
And it's going is one now I read from the Nitrate or the Eddie.
So this is element, compare it to what they have to do, we have to subtract.
So what will happen?
I will make the count zero.
OK, three and two, they are different.
So I will do count minus minus.
I will make the count zero after doing the count zero.
That means this is not my majority element because the count zero.
So I will update.
So my new candidate element is basically two and my count is one.
Now I am saying that two is the candidate for the majority element and disappearing one time.
Now let us continue our so I have elementary.
So elementary is basically different than to what I will do.
I will subtract.
OK, you can see here.
So what we can do, we can see here.
Is the majority element, I'm subtracting the majority aluminum, subtracting the count from all of
that element.
OK, and if it is a majority, it will appear it will exist till then.
OK.
Now, 20, 20, they are different, so I will subtract.
So the count will become zero if the count becomes zero.
It's time to update your candidate for the majority elements who can read history.
And the count is basically one.
Then what will happen?
Let us continue attracting the ordinary.
Now the jury will finish and your candidate is basically three, which is your answer.
In this case, three is the answer.
So that's how it is working.
Let us take this example also.
OK, so this is two to one one.
One, two, two.
So let's take this example to two, then I have one, one and one, then I have to do what we have to
do.
We have to assume first.
So let us assume this is the candidate for the majority element.
OK.
So the candidate is basically do and each count is basically one.
OK, so two is the candidate for the majority element because initially I have to assume, OK, now
let's continue our trading already.
So to two and two, they both are slim.
So what I will do, I will increase the council count plus plus or count will become two now one and
two, they are different.
When is the current element and two I am assuming is the majority element since the candidate is different,
elements are different.
I will do count minus minus so count will become one.
So what I am doing if same.
Then mattilda, count, placeless, if different in the elzbieta, they are different if different.
I will do count minus minus and if the count becomes zero, if the count becomes zero, that means update
your majority element to update your candidate for the majority element.
OK, now compare one with two.
So they are different.
They are different.
And what will do count minus minus count will become zero.
As soon as the count will become zero, it's time to update your majority element.
So now the candidate is won, OK, now the candidate is won and its count is one.
OK, one is updating one time.
Now let's continue our trading order.
So I have one.
I have one.
So I will do count plus plus or count this to.
I have to so what I will do, so I think this is one.
OK, so I have to and this is the candidate element.
This is the majority element, which is one what will do I will do count minus, minus account becomes
one.
Now, again, I have to say no to anyone.
They are different.
So they will look on to minus minus since the count becomes a zero.
If the count becomes zero.
It's time to update their majority element.
So the majority element is two and it's counted one.
OK, so the majority element is to end its count is one.
Finally, your error will end and this is your answer.
OK, this is our majority element.
This is the answer.
So algorithm is very simple.
What we are doing, we are subtracting.
So Element E is the majority element.
So subtract the count of majority element from the rest of the elements since E is the majority element.
So it will remain till the end of the year.
It will exist till the end of the year.
So in this case, how many times two is appearing.
So two is appearing.
One, two, three, four.
So two is appearing four times.
How many times different elements are appearing so different.
These three are different elements than the majority element.
So the rest of the elements are appearing three times.
So if you subtract the count.
OK, the count, so the count is one, so basically, if you will subtract the count, since it is the
majority elements or two will exist till the end.
That's why two is existing till.
Let's take one more example.
Then after this example, we will write the code.
OK, so four seven four four seven four four and nine four three logic is very simple.
I will compare the current element of the eddy with the candidate, with the majority element candidate
if they are same.
I will do countless place else, but they are different if they are different.
I will look on minus minus if the count becomes zero.
That means it's time to update the candidate and update the majority of their candidate element.
Now, initially, I don't know which is the majority element.
So my candidate is basically four and the count is basically one.
OK, for disappearing one time.
Now let's get rid of a diary.
OK, let's start out reading.
Seven, seven and four.
They are different if they are different, I will look out minus minus this account becomes zero.
If the count zero, it's time to update OK, the count update.
So seven is the candidate element and its count is one.
Seven is appearing one times again, four.
So four and seven, they are different.
So if they are different, Waterloo count minus minus so count becomes zero.
If the count zero we will update the majority element.
So four and the count of 47 for disappearing one times again after.
So make the count to 14 for the same.
So that's why the count.
Plus.
Seven, seven and four, they are different, so to minus minus, so count becomes one.
Again, for so foreign food, there seems to count placeless again for so foreign food, there seems
to count placeless.
Nine and four, they are different, so minus minus.
Four and four, OK, four and four that seem so complex plus.
Three and four, they are different.
So count minus, minus.
Now, finally, you are.
So since Ford was the majority, elements of Ford will appear till the end of the year.
So what is the answer?
The answer is basically the candidate element, which is for you can see yourself how many times Ford
is appearing.
So one, two, three, four, five and six.
So Ford is appearing six times.
And the rest of the elements since the ad is basically after distance or the rest of the elements are
appearing four times, if you will subtract six minus four, which is to OK, this two and two.
OK, this is same.
Since Ford was the majority element of the majority element from the rest of the element, so the majority
element will exist till the end.
This is the main logic.
OK, so this is the majority element.
And it's found after subtracting from the older elements as to, OK, you can see two.
This is the approach, this is the Andalusians and Putin is very simple.
So if you find out a different element, you have to subtract.
Now, let us write the code.
OK, so I have to retain the majority element, then I have the functional majority element and let's
see the name of the vector is a.
So very simple approach, what is the candidate, so candidate is the first element, Joselo.
And it is appearing one time, OK?
So this candidate is the candidate for the majority element.
Now, let us find out the size, so the size is basically a large size.
And now let us it over, Daddy.
OK.
So I have to start out reading from one.
So I lived in Indianapolis bliss.
Again, very simple condition, if the elements are slim, if the current element.
It seems the candidate element then you have to do count placeless.
In the elzbieta, but you have to do the elements are different.
You have to do count minus minus.
And after doing minus minus, if the count becomes a zero.
If the count becomes suicidal.
That means it's time to update your candidate element, so my candidate element is the current element
and the current element is appearing one times.
OK, finally, since we can assume that the candidate that the majority element always exist.
So you are present in the variable candidate.
OK, let's get another caller.
OK, now let's meet gold.
OK, so basically our code is working fine.
So what is the time in the space complexity?
So what is the time and the space complexities?
So the time complexity is big.
Often what we are doing, we are just iterating over the edge and the space complex, it is big of one.
OK, so this is the time in this space complexity.
Now, one more thing here, what we are doing here, we are assuming that the majority element always
exist.
Now, what if the majority element do not always exist?
OK, so what if we do not?
We cannot assume so if we cannot assume what we have to do.
So if we cannot assume what we have to do, we have to find the count of the candidate element.
OK.
Now, what we can do, let us take a variable.
Count two, OK, at the security will count do so.
What we're doing, let us assume.
So we cannot assume that the majority element is always there.
OK, we cannot assume majority element is always there.
So we will check first.
OK, so we will check first.
So let's sit right over the Eddie.
We cannot assume so we check.
So we check whether the candidate element is majority element or not.
OK, so what you have to do, you just have to find it count.
So if the current element is it goes to the candidate element, then will do we will do count two plus.
Plus.
Okay, count two plus plus.
Finally, we know the count of the candidate element, so basically if the count.
OK, count two is basically good end by two, so that means the majority element is dead.
So if the majority element is dead, I can return.
The candidate element in the Elzbieta majority element do not exist.
OK, so if the majority element do not exist, then minus one because we have to return an integer.
So I'm returning minus one.
OK, now let's meet our called.
OK, so our court is working fine now, why this court is working fine, so this court is working fine
because in the end it is given that the majority element is almost there.
OK, in the question it is given that the majority element is always present.
So that's why you will always be able to find a candidate element.
You will always be able to find a kindred element whose account is basically guerdon and vital.
So in every condition, in every input, this written statement will be executed.
OK, we will never reach the part.
We will never reach the part, OK, because in the question it is given the majority element always
exist.
Now, let us summarize.
So we discussed four approaches to solve this question, so first one was the brute force approach.
So in the brute force approach, time was and square and the space was big.
Often the second was Hashmat approach.
So time was big often and the space was also big.
Often the third was deciding approach.
So the time was at Logan and the space was big.
Often.
Now the best approach is basically this more voting algorithm, Woody's voting algorithm.
And basically that time is big off and the spaces because one.
OK, then, to this very simple, it will subtract, if you will, separate the majority element, which
is element, it also protect the majority element from the rest of the elements, since this is a majority
element.
So it will appear till the end of the year, it will exist.
And of the area, we are doing exactly the same.
OK, we are doing exactly the same here.
I'm assuming this is my majority element and I am over the area.
If this is a majority element, it will exist till the end of the area.
OK, it will exist till the end of the year.
So this is a very famous question, OK, so if you have any doubt in this question, you can ask me,
OK, thank you.