Majority Element ｜ Brute- Better-Best Approach ｜ M..
Majority Element ｜ Brute- Better-Best Approach ｜ M..
Category
📚
LearningTranscript
00:00Hi everyone and welcome to the complete DSA series in which we are going to study 2 more
00:09questions of array which are pair-sum and majority element.
00:11If we want to study any other concept or question in DSA then it will be available in this playlist
00:17on this channel.
00:18So let's start with our first question which is called pair-sum.
00:24The question of pair-sum says that we have a given sorted array.
00:28Sorted array means that either all the elements are arranged in ascending or descending order.
00:33Here we know that our array is sorted in ascending order.
00:37So in this way, we have a given array and we are also given a target sum.
00:43For example, let's suppose target is equal to 9.
00:46In this entire array, we have to return a pair of two numbers whose sum will be equal to 9.
00:53For example, if we take the example of this array, the sum of 2 plus 7 is 9.
00:58So we have to return 2 and 7.
01:00Or we can also return the index of 2 and 7.
01:02So this is index 0, 1, 2 and 3.
01:04And we have already been given in the question that there will always be some valid and unique answer.
01:09So this is an easy level question and it is really easy.
01:12First of all, let's talk about its brute force approach.
01:15If we have been given an array and I know that I have to get a pair from it whose sum is equal to the target.
01:20So the first brute force approach that will come to mind is that why not I get all the pairs.
01:27I get all the pairs of this array.
01:30And in those pairs, whichever sum is equal to my target.
01:34If the target is equal to the pair-sum, then I will return the index of those two numbers.
01:41How to return the index?
01:42We can store both the index values in a vector and return them.
01:47For example, there can be many pairs in this array.
01:50The pair of 2 can be formed with 7.
01:52The pair of 2 can be formed with 11.
01:54The pair of 2 can be formed with 15.
01:56If we talk about 7, then the pair of 7 can be formed with 11.
02:00The pair of 7 can be formed with 15.
02:01If we talk about 11, then the pair of 11 can be formed with 15.
02:04So these are all unique pairs that can be formed inside the particular array.
02:08So, if we want to get all the pairs, then I know that I have to pair 2 with next element, then with next element, then with next element, I have to pair 7 with its next element and with its next element.
02:20I don't have to go backwards, because even if it is a pair of 2 and 7, even if it is a pair of 7 and 2, it is basically the same pair that we are talking about.
02:27So, we will just try to get unique pairs.
02:29So, to get pairs in any array, first of all, we pick the first element of the pair.
02:36First element, we will go from i is equal to 0 to i less than n i plus plus.
02:41And what will we make each element? We will make our first number, the first number of the pair.
02:46So, if the first number of the pair is 2, then all the next numbers will be the second element of the pair.
02:53So, we have to make one more loop for integer j equals i plus 1.
02:59If this is already the first element, then to make a pair of 2 and 7, it has to start with i plus 1, then i plus 2, then i plus 3, until our array is running.
03:09So, we will start with i plus 1, j less than n, j plus plus.
03:13So, what are the pairs made? We have made one pair of i and jth element.
03:18So, in this way, we can make a nested loop and get the pairs of i and j.
03:22So, in this way, we can get the pairs of i and jth element.
03:28So, how can we check? Basically, we can check that if our array of i plus array of j, which is basically the pair sum, if its value is equal to our target,
03:41So, in this case, we will simply push back our i in the vector.
03:46So, we have already studied the operations of vectors.
03:50And we will push back our j in the vector.
03:53And finally, we can return our vector from here.
03:57Vector is nothing. It is an answer array like structure.
04:00And we can return our answer from here.
04:02If this thing is not satisfied, then we will check for the next pair of i and j.
04:07So, first, we will check for 2 and 7.
04:09If we check for 2 and 7, then we will get the answer here.
04:12But, let's suppose, we have 13 instead of 9 in the target.
04:16So, if we check for 2 and 7, then answer will be 9.
04:199 is not equal to 13.
04:21Then, if we check for 2 and 11, then answer will be equal to 13.
04:25And finally, we will return our index 0 and 2 as our answer.
04:29So, this approach is our brute force approach, whose time complexity will be equal to big of n square.
04:34Why is it equal to big of n square?
04:35Because we have used another nested loop in one loop.
04:38So, let's code it once.
04:40We are going to code it quickly.
04:42Because this is not the most optimized approach that there is.
04:45Here, the value of n will be equal to nums.size.
04:50In fact, we can write this whole code in the form of a function.
04:54Vector of integer will be our return type.
04:57We will call it pairSum.
04:59In pairSum, we will get vector nums and a target.
05:05Finally, we have to return this vector of integer.
05:08Here, we will get our code.
05:10And, let's make a vector of integer as our answer.
05:14So, this is our overall logic.
05:17j is equal to i plus 1.
05:19We have to start with i plus 1 for all the pairs.
05:21j less than n.
05:22j plus plus.
05:24Every time, we will check if the value of nums of i plus nums of j is equal to our target.
05:31If this value is equal to target, then we have to push back our i in the answer.
05:37After that, we can push back our j.
05:40And, finally, we are going to return our answer.
05:42Otherwise, we can return the empty answer at the end.
05:45But, because the answer will always exist, this is the statement that will be executed for some pair.
05:52So, this is what the code is going to look like.
05:54Let's also test it.
05:56We will get the answer of vector of integer from pairSum.
06:00After passing nums and target, we will get cout in it.
06:06Answer index 0 and answer index 1 with end of line.
06:17Let's save it and run it.
06:19So, we will get the answer 0 and 1.
06:21How is it 0 and 1?
06:22Because, sum of 2 and 7 is 9.
06:24Similarly, if we do 13, then we will get 0 and 2 in the answer.
06:28So, we will get these two indexes.
06:31Now, nested loops are used in this.
06:33This is our brute force approach.
06:35We have one more optimization on this which exists.
06:38How will we know this optimization?
06:40Basically, we have already given in the question that my array is a sorted array.
06:45In brute force approach, I know that I got big O of n square time complexity.
06:49So, we will use a better approach than this.
06:51Now, in the question, I did not use sorted array.
06:55When I took out all pairs in brute force approach, then my array is already sorted.
06:59I did not take advantage of this.
07:01In coding questions, generally, any information is given to you.
07:04So, any information is not irrelevant.
07:06Every information has some use in the answer.
07:10Either it is used for optimization or it is used to think of a corner case.
07:14So, the sorted array is used to reduce my time complexity.
07:19It will help me to get a more optimized answer.
07:22Basically, if I already have a sorted array in ascending order,
07:26we are talking about an optimized approach.
07:28If there is already a sorted array in ascending order,
07:31then I know that my small elements will exist in the beginning
07:34and my big elements will exist later.
07:36So, if I take the sum of the elements in the beginning,
07:39then what will be the value?
07:40The value will be small.
07:41So, the overall sum will be small.
07:42If I take the sum of the values in the beginning,
07:44then the overall value will be a little big.
07:46So, why don't we use our two-pointer approach here?
07:50How will we use the two-pointer approach?
07:53Basically, we will take a pointer.
07:55One pointer is in the beginning.
07:57We can call this pointer as i-pointer.
08:00And we will take one pointer, which we will call as j-pointer.
08:04We will start i-pointer from the beginning and start j-pointer from the end.
08:09So, we will get the sum of the smallest and biggest elements of the array.
08:14Now, what do I have to do with this sum?
08:16Whatever pair sum I get,
08:18I have to compare this sum with my target.
08:22And when we compare this sum with our target,
08:25there can be three cases.
08:27Either the pair sum can be bigger than the target,
08:30or the pair sum can be smaller than the target,
08:33or the pair sum can be equal to the target.
08:36These are the three particular cases that can exist.
08:39For example, if the target value is 9,
08:42and the value of the pair sum is 2 plus 11,
08:46which is equal to 17.
08:48So, this is the case where the pair sum is bigger than the target.
08:51This is the first case.
08:53So, if we get the first case,
08:55can I say that I have a bigger number?
08:57I don't want a bigger pair sum.
08:59I want to get closer to the target.
09:01So, who made the pair sum bigger?
09:03The last number that we added,
09:06we didn't want to add such a big number in the target sum.
09:10We wanted to add a smaller number in the pair sum.
09:14And what is a smaller number than this?
09:17This is a smaller number than this.
09:19So, what we will do is,
09:21if our pair sum is bigger than the target sum,
09:24then we will take the bigger value in the pair sum
09:27to the smaller value.
09:29So, here we will make our j minus.
09:32Because our sum is bigger than the required value.
09:35Now, let's take another example.
09:37Let's suppose that our j is on the last index,
09:39and our i is here.
09:41What we will do is,
09:43this time we will take our target as 26.
09:45If the target is equal to 26,
09:47and here we took out the pair sum,
09:49which is 2 plus 15,
09:51which is equal to 17.
09:53Now, we know that if the pair sum is 17,
09:55then it is smaller than the target.
09:57So, we need to increase this pair sum in some way.
09:59And when do numbers increase in ascending order?
10:02Numbers increase as we move forward.
10:05So, to increase the sum of our pair,
10:07I need to take a bigger number than 2.
10:10We cannot increase this,
10:12because this is already the biggest possible number.
10:14So, what we do is, whenever we want to increase the number,
10:16we upgrade the smaller number to the next value.
10:20So, the second case will be,
10:22if the value of the pair sum is smaller than the target,
10:24then in that case, we will make our i plus.
10:27When i is plus plus, then i will come here.
10:29Now, what is the new pair sum?
10:31The new pair sum is 7 plus 15,
10:33which is equal to 22.
10:35So, here the pair sum is 22.
10:37The pair sum is still smaller than the target.
10:39So, case 2 is coming.
10:41In this also, we will make i plus plus.
10:43So, i plus plus will come here.
10:45This time, the pair sum is 11 plus 15,
10:47which is equal to 26.
10:49Here, the pair sum finally becomes equal to the target.
10:52Now, as soon as the pair sum becomes equal to the target,
10:54we hit our case 3.
10:56In case 3, we will return our answer.
10:58And what is the answer?
11:00The answer is the pair of the current i and j.
11:03So, whenever we start and end with two pointers,
11:07in a sorted array,
11:09when we talk about pair sum and target sum,
11:11then only three cases exist.
11:13On their basis, these three conditions can be applied.
11:15The logic that we are using here is,
11:17when we are adding a very small value and the biggest value,
11:22if the value is getting smaller by adding,
11:24then we need to remove this small box and get a bigger one.
11:28And if the value is getting bigger by adding,
11:30then we need to remove this and get a smaller box.
11:33We are working on this logic.
11:35When the value fits perfectly,
11:37then we get our answer.
11:39So, its approach will be like this.
11:41We will take two pointers.
11:43We can start i from 0.
11:45We can start j from n minus 1.
11:47In a two-pointer approach,
11:49we have to go till the time
11:51the value of i is less than j.
11:54So, till the time while i is less than j.
11:57We are not writing equal to here
11:59because we don't want j to be equal to i.
12:01Because if j is equal to i,
12:03then i will also be equal to i and j will also be equal to i.
12:05And this will not be a pair.
12:07Pair can only be made between two different numbers.
12:09So, here we will check for our first condition
12:11that if our pair sum,
12:13or let's calculate the pair sum,
12:15pair sum is going to be equal to
12:17array of i plus array of j.
12:19Let's remove them from here.
12:21Here, we will basically check
12:23that if our pair sum is greater than our target,
12:25then in that case,
12:27we have to make j equal to minus minus.
12:29The second case will be
12:31else if.
12:33If the pair sum is less than the target,
12:35then in that case, we have to make i equal to plus plus.
12:37And in the case of else,
12:39we will finally return
12:41the pair of i and j.
12:43So, in every iteration,
12:45one of the three conditions will be true.
12:47Either we will return the answer
12:49or we will have j minus minus
12:51and i plus plus.
12:53So, in this way, we will solve our approach.
12:55Because in the worst case scenario,
12:57i is going from the front to the back,
12:59j is coming from the back to the front.
13:01So, somewhere, i and j will be meeting
13:03in the worst case scenario.
13:05This loop will stop in the worst case
13:07when the value of i will be equal to j
13:09and we will come out because of this condition.
13:11So, in that worst case also,
13:13we would have traveled the entire array once.
13:15And that is why the time complexity of this code
13:17So, let's convert this entire approach
13:19into the code.
13:21In this function,
13:23I am going to remove all of this
13:25and take i and j.
13:27We will start i from 0
13:29and start j from n minus 1.
13:31While i is less than j.
13:33Till then, what do we have to do?
13:35First of all, we have to get our pair sum.
13:37Pair sum is equal to
13:39nums of i
13:41plus nums of j.
13:47In the first case,
13:49if the value of pair sum
13:51is less than target
13:53or greater than target.
13:55If this is greater than target,
13:57then we have to do j minus minus.
13:59Else, if pair sum is less than
14:01target,
14:03in that case, we have to increase the start pointer.
14:05And in the case of else,
14:07we will simply push back
14:09our values in the answer.
14:11Not 1, but i
14:13and j.
14:15We will return our answer
14:17from here.
14:19This is our overall approach.
14:21In this case,
14:23this is our time complexity.
14:25We don't have to do anything here.
14:27We just have to print our answer.
14:29If our target is equal to 13,
14:31the answer will be 0 and 2.
14:33If our target is equal to 26,
14:35the answer will be
14:37equal to 2 and 3, i.e. 11 plus 15.
14:39This is how we solve our problem
14:41of target sum.
14:43It is called majority element.
14:45It is a classical question
14:47when we talk about arrays.
14:49In our DSA sheet,
14:51this is the first question called majority element.
14:53You will get the link for it.
14:55The link for DSA sheet is given below.
14:57You can access it from there.
14:59This is the question that I am talking about.
15:01It is called majority element.
15:03It is an easy level question.
15:05Given an array nums of size n,
15:07return the majority element.
15:09We will get an array similar to this.
15:11In this, we have to return
15:13a thing called majority element.
15:15What is majority element?
15:17It is the element that appears
15:19more than floor n by 2 times.
15:21In this way, we are saying
15:23floor n by 2 times.
15:25The basic meaning of floor n by 2
15:27is that if you
15:29divide 8 by 2,
15:31the value will be 4.
15:33But if you divide 9 by 2,
15:35the value will be 4.5.
15:37In the case of 4.5, we have to consider 4 only.
15:39Majority element should exist
15:41greater than 4 times.
15:43Floor doesn't mean anything.
15:45Floor means like
15:47integers are calculated in C++.
15:49It means the same.
15:51Our question practically says
15:53that majority element, let's call it mj,
15:55should exist greater than
15:57n by 2 times in this array.
15:59At least
16:01more than half of the array
16:03should have the same element.
16:05That is why it is majority element.
16:07Assume that majority element always exists in the array.
16:09We are given that
16:11majority element will exist.
16:13This is given in the question.
16:15First of all, we will solve this question
16:17using brute force approach.
16:19After that,
16:21we will optimize this question a little bit more.
16:23After that,
16:25we will discuss the most optimized approach of this question
16:27which is called Moore's voting algorithm.
16:29If you have already done this question using brute force approach,
16:31then timestamps are given to you.
16:33If you want, you can directly go to Moore's voting algorithm
16:35and skip it.
16:37First of all, we will discuss the brute force approach.
16:39We have to find the majority element.
16:41I know in a way that
16:43the frequency of my element
16:45means
16:47how many times that element
16:49is coming in my array.
16:51The frequency of that element
16:53should be more than n by 2.
16:55I already know this.
16:57In this question, the value of n
16:59is equal to 5.
17:01That means the majority element
17:03should exist greater than 2 times.
17:05Greater than 2 means
17:07the majority element can come 3 times, 4 times
17:09and 5 times.
17:11In my mind, the brute force approach will be
17:13that if I have to find the element
17:15whose frequency is the highest
17:17then why not
17:19find the frequency of all the elements
17:21and
17:23the element whose frequency is the highest
17:25will be my final answer.
17:27In fact, it will not be the highest.
17:29I know that the majority element
17:31exists in more than half of the array.
17:33So, it can be only one element
17:35in some array.
17:37If some element occupies more than half of the array
17:39then the other element can never occupy
17:41more than n by 2.
17:43So, only one majority element
17:45will always exist.
17:47If only one majority element exists
17:49then I will find the frequency of all the elements.
17:51The element whose frequency is greater than
17:53n by 2 will be my majority element.
17:55How do we find the frequency of all the elements?
17:57I will basically
17:59go to each and every element.
18:01Let's suppose I go to 1.
18:03Here, I know that my element is 1.
18:05Now, I will check in the entire array
18:07that how many times does 1 exist.
18:091 exists once, twice and thrice.
18:11So, what will be the frequency of 1?
18:13It will be 3.
18:15Here, I will find that
18:173 is greater than n by 2.
18:193 is greater than 2.
18:21So, 1 is my majority element.
18:23If 1 is not here
18:25let's suppose
18:272 is here and 1 is here.
18:29In that case,
18:31let's go to 2.
18:33For 2, let's calculate its frequency.
18:35Let's run the loop on the entire array.
18:372 exists once, twice.
18:392 exists twice.
18:41But 2 is not greater than n by 2.
18:43So, it cannot be the majority element.
18:45Let's go to the next element.
18:47Here, 2 also exists.
18:49Let's check for 2.
18:512 exists twice in the entire array.
18:53Let's go to 1.
18:552 exists thrice in the entire array.
18:57So, the frequency of 1 is 3.
18:593 is greater than n by 2.
19:01So, 1 is my majority element
19:03which is my final answer.
19:05Brute force approach says
19:07to pick all the elements one by one.
19:09For any vector,
19:11let's suppose
19:13I have run the loop on integer nums.
19:15What did I do?
19:17I picked all the values one by one.
19:19Let's suppose
19:21I picked 2 in the beginning.
19:23Now, I will run another loop
19:25on the entire array or vector.
19:27Let's call it
19:29element in numbers.
19:31If
19:33this element
19:35becomes equal to my value,
19:37then I have to
19:39make the frequency
19:41plus.
19:43Let's take a frequency element
19:45and initialize it with 0.
19:47First, I took 2.
19:49As soon as I got 2,
19:51I ran a loop on the entire array
19:53or vector.
19:55Wherever both the numbers are same,
19:57where I got my value,
19:59I will make the frequency plus.
20:01As soon as the loop ends,
20:03check
20:05if the frequency
20:07becomes greater than n by 2.
20:09In that case, I got
20:11my majority element.
20:13So, this is my brute force approach
20:15in which I am using another loop.
20:17That is why brute force approach
20:19is going to take big of n square time.
20:21Let's write it in our code.
20:23Here, we can write the same
20:25approach for
20:27integer value
20:29in numbers.
20:31First, we are taking the value.
20:33Here, we will initialize
20:35the frequency with 0.
20:37We are not counting the number of times
20:39the element is occurring.
20:41We will count the frequency
20:43in the second loop.
20:45For integer,
20:47I have written element as el
20:49in numbers.
20:51If my element
20:53is equal to my value,
20:55in that case,
20:57the frequency will be plus.
20:59When the entire loop ends,
21:01check if the frequency
21:03is greater than n by 2.
21:05What is this n by 2?
21:07Integer n
21:09is basically nums.size.
21:11If the frequency
21:13is greater than n by 2,
21:15we will return
21:17the value from here.
21:19The answer is the majority element.
21:21I know that majority element
21:23will always exist.
21:25This is already given in the question.
21:27This condition will be true
21:29and the value will be returned.
21:31If the value is not returned,
21:33we can write minus 1 here
21:35but this statement will never be executed.
21:37If we run this code,
21:39all the test cases
21:41will be cleared
21:43but this is not
21:45the best way to solve this question.
21:47There is a better approach
21:49than brute force
21:51which is based upon sorting.
21:53Students who have already
21:55studied sorting,
21:57will understand this approach
21:59otherwise we will study sorting later.
22:01Approach says that first
22:03sort the entire array.
22:05When we sort the array,
22:07small elements will be sorted in ascending order
22:09and big elements will be sorted later.
22:11It will take time to sort
22:13big of n log n is equal to 1.
22:15The second step is
22:17to run a loop on the entire array.
22:19The loop time complexity
22:21will be equal to big of n.
22:23We will go to one element
22:25and since it is a sorted array,
22:27all the same elements
22:29will be there in a continuous manner.
22:31We will calculate the frequency
22:33of all the elements in a continuous manner
22:35in the same loop.
22:37Here we came to 1,
22:39then 2 at next 1
22:41and 3 at next 1.
22:43Here I came to know that
22:453 is greater than n by 2 i.e.
22:47this is my majority element.
22:49If we take an example,
22:51for example we have array
22:53with elements 0,0.
22:551,1,2,2
22:57and 2
22:59Here n is equal to 9.
23:01It is already a sorted array
23:03so we started from here.
23:05Since elements came first time,
23:07because it is first time, so its frequency will be equal to 1
23:10then in next iteration, if we go to next 0, then frequency will be equal to 2
23:14now when we will update our index again
23:17so here our element has changed, here our element is different from the previous element
23:22so in this case what I have to do, in this case I have to reset the frequency again to 1
23:26now here some student must be thinking that the frequency of 0 is lost
23:30so his answer is that the frequency of 0 is lost, it doesn't matter
23:33because 0 was not a majority element
23:35if it was there, then we would have got the majority element earlier
23:38because it is not a majority element, so we have deleted its frequency and made it 1 again
23:42it will not make any difference
23:44after that, if we update our index again, then the frequency will increase
23:48it is equal to 2, still it is not a majority element
23:50after this, if we update the index again
23:53here the change from 1 to 2 has come
23:55so again we will remove the frequency of 1 and reinitialize this value from 1
24:00it doesn't matter if the frequency of 1 is deleted because it is not a majority element
24:04if we update here, then the frequency will become 2
24:06till the same numbers are coming, we have to update the frequency
24:09and as soon as the number is different, we will reset the frequency to value 1
24:16now here in the last also 2 came, the frequency became 5
24:18as soon as it became 5, this value became greater than n by 2
24:21greater than n by 2 means that we got our majority element
24:25so in the second, our sorting approach, first of all we sort the array
24:29to sort the array, as such we don't need to use any fixed sorting algorithm
24:33we can use the function of our inbuilt sort, we will see it directly in the code
24:38in the second step, we can pick the element in the beginning
24:40first, we will take the frequency, we can initialize the frequency with 1
24:44and the element or the answer, we can initialize it with nums of 0
24:52means the first element in the sorted array, we have assumed it to be the majority element
24:56after that, we will run our loop, so we have already counted the first in the frequency
25:00we will start our loop from i is equal to 1, i less than n, we will make i++
25:06after that, every time I have to check, if my nums of i value
25:10means if we have come on this index, on the next index
25:13so we have to check if it is equal to the previous one
25:15if it is equal to the previous one, then we will update the frequency, we will make the frequency plus plus
25:20but as it is 2, 2 is not equal to 1, means here I have to reset the frequency
25:25so there can be only two situations, either my nums of i is equal to the nums of i minus 1
25:32if it is equal to, then we have to make the frequency plus plus
25:36and in the case of else, we have to reset the frequency to 1
25:41plus, the answer will change this time
25:44because we did not get the majority element, so what will be the answer?
25:48the answer will be nums of i, which is our current element, we will assume it as our answer
25:54for example, if we have an array 1, 1, 2, 2, 2
25:59so we are assuming this array, we have already sorted it
26:02after that, we are trying to run our loop on this
26:05when we will run the loop, we will see, first we came on 1
26:08for 1, we kept the frequency as 1, and here we stored 1 in the answer
26:13we will start this loop from this 1, this 1 is equal to the previous 1
26:17so it means, we will make the frequency plus plus, the frequency will become 2
26:21after that, we will run the loop again
26:23next time, we will come on this 2
26:25here, the frequency is already 2
26:27but when we will compare 2 with 1, then 2 will not be equal to 1
26:31it means, I have to reset the frequency, and the answer will be equal to 2 this time
26:36and every time, as soon as we calculate the frequency, whether it is plus plus or reset
26:40every time, we can check, if our frequency is greater than n by 2
26:45so we will return, whatever is the stored value of this value in our answer
26:51so this is the optimization on brute force, and our overall approach to solve this question is using sorting
26:58in the first step, sorting will be done, so it will take big O of n log n time
27:01plus, in the second step, only one loop is running, so it will take big O of n time
27:05so overall, the time complexity that comes here
27:07that comes equal to big O of n log n
27:12and this algorithm is faster as compared to this algorithm
27:15so let's convert this into code
27:17so in code, the first step is to sort our array
27:21now to sort, we can use the sort function
27:24which does the work of sorting the vectors
27:26in this, first of all, we pass the beginning pointer of the vector
27:29which we get using nums.begin
27:31and then we pass the ending pointer, which we get using nums.end
27:35so from these two functions, the beginning and ending pointer will come, and our number vector will be sorted
27:40the second step is that we have to count the frequency
27:43so for the second step, first of all, let's take our frequency, which is equal to 1
27:47and assume our answer to be nums.zero
27:50then we have to run a loop for integer i equals to 1
27:54because we have already assumed the answer to be zero
27:56i is less than n, i is plus plus
28:00every time we will check, if our nums.i is equal to our previous index number
28:06then we are talking about the same number
28:08then we simply have to plus plus the frequency
28:10and in the case of else, we will reset the number
28:14which is frequency becomes equal to 1
28:16and our answer will also be nums.i, which is the new number
28:20and every time, as soon as the frequency is updated or anything happens
28:23we have to check every time, in every iteration, if frequency is greater than n by 2
28:28if the frequency is greater than n by 2
28:31then in that case, we will return our answer, which is the majority element
28:35and in the last, we will return our answer
28:40so this is our overall code, let's run it
28:43our test cases are accepted, we can also submit it
28:47this is the solution of nlogin, which will be accepted
28:50but there is one more optimized solution than this, which is Moore's voting algorithm
28:55and it is an important concept, which we should know
28:59so we are going to discuss this concept in detail
29:02so for moore's voting algorithm, let's talk about intuition first
29:09intuition of this algorithm says
29:12if such a majority element, whose frequency is greater than n by 2
29:18exists in this array
29:21so moore's voting algorithm says
29:23if we start tracking the frequency of all the elements from the beginning
29:29then the frequency of majority element will always be the highest
29:33basically, if we imagine frequency as a power
29:37every element, with the frequency and count
29:41means it exists in that array with the same power
29:44like if we take an example of this particular array
29:47so moore's algorithm says, you don't even need to sort the array elements
29:51what you have to do is, simply count the frequency of the array elements
29:56and take your answer, which is very similar to the sorting approach
29:59but this time, you don't have to sort
30:01this time, you simply have to run a loop
30:03in which you start with your first element
30:06take the frequency of the first element, which is equal to 1
30:08make the answer as 1
30:10and what you have to do is, as soon as a different element comes
30:13this frequency is like a power in the voting algorithm
30:17or we can understand it as votes
30:19as soon as the frequency comes
30:22so if we get the same element
30:24then we have to make the frequency plus plus
30:26means in the case of same element
30:28we have to make the frequency plus plus
30:30because it is the same element
30:32but as soon as a different element comes
30:34moore's voting algorithm says
30:36this time you don't have to reset the frequency
30:38you don't have to reset because there is no sorted array this time
30:41because if you reset that element, then that element can come in front
30:44so instead of resetting, this time we will make the frequency minus minus
30:48and because frequency is equivalent to the power
30:51so the frequency of the majority element will be so high
30:54that you will make it minus minus
30:56still eventually, in the last
30:58after this entire loop
31:00the highest frequency will be of the majority element
31:03means when we count the majority element
31:06then it will give such a high frequency
31:08that the other elements will try to make its frequency minus minus
31:12still the winner will always be the majority element
31:16why? because the frequency of the majority element is greater than n by 2
31:19it exists in more than half of the array
31:21so the frequency will have a value greater than n by 2
31:24and these values will be less than n by 2
31:26so when these values will try to make it minus minus
31:29still the higher or the frequency of the majority element
31:32at the end of the loop
31:34can never be zero
31:36if the majority element exists
31:38so basically if we start the frequency with zero
31:41and there is nothing in the answer
31:43let's suppose zero is stored
31:45so we can run an entire loop on this array
31:48for integer i equals zero
31:50i less than n
31:52i plus plus
31:54every time that loop will run
31:56and what we will do
31:58if the frequency value is zero in the beginning
32:00then we will make this number our answer
32:02so if at any point
32:04my frequency becomes equal to zero
32:06so in that case my answer is going to be
32:08nums of i
32:10then we can check
32:12if we are on the same element
32:15and if we are on a different element
32:17then we will make the frequency minus minus
32:19so if the value of our answer
32:21becomes equal to
32:23nums of i
32:25means we are on the same element
32:27in that case I have to make the frequency plus plus
32:29and in the case of else
32:31I have to make the frequency minus minus
32:33and moore's algorithm says
32:35because the frequency of the majority element
32:37will be greater than n by 2
32:39so as soon as this loop ends
32:41the value in the answer at the end
32:43will be the value of the majority element
32:45so in the end we don't have to do anything
32:47we just have to return our majority element
32:49after the loop ends
32:51so from here we will return our answer
32:53so this is how the moore's voting algorithm works
32:55and its time complexity is
32:57big of n is equal
32:59because we are not sorting anything
33:01we are running a simple loop
33:03and this algorithm is so sophisticated
33:05as a beginner it is not easy to think of moore's algorithm
33:07but this algorithm is very simple
33:09easy to understand
33:11it relies on the same thing
33:13that if I have a lot of candidates
33:15like there are a lot of candidates in voting
33:17it is possible that a candidate
33:19may lose in Delhi or Gujarat
33:21or may lose in Maharashtra
33:23but in other places
33:25the majority of that candidate will be
33:27that when the overall frequency is counted
33:29then the same candidate
33:31will always come out in our final answer
33:33this simple logic
33:35our algorithm works on
33:37so the whole logic we have seen
33:39lets convert it in code
33:41first initialize the frequency with 0
33:43and initialize the answer with 0
33:45I have to run a simple loop
33:47from i equals 0 to i less than n
33:49i plus plus
33:51first we will check
33:53that if our frequency is 0
33:55now if our frequency is 0
33:57then what I have to do
33:59I have to make my new element my answer
34:01so answer is going to be
34:03equal to nums of i
34:05whatever new element is running
34:07after this we have to check
34:09if our answer is equal to
34:11nums of i
34:13means we are talking about same element
34:15in that case frequency will be plus plus
34:17and in else case frequency will be
34:19minus minus
34:21and finally
34:23in last we will return our answer
34:25and with this much algorithm
34:27we need to write
34:29lets make nums.size
34:31and this will be frequency equal to
34:33lets run it
34:35our test case is clear
34:37we can submit this code
34:39and our answer is successfully submitted
34:41so in this way we apply
34:43our algorithm
34:45lets run it dry
34:47on this particular array
34:49which is already given
34:51so we are starting
34:53with frequency equal to 0
34:55and in start our answer value is also 0
34:57we started
34:59first we went to this index
35:01here we have 1
35:03our frequency is 0
35:05if frequency is 0
35:07so in that case we initialize
35:09answer with this value
35:11so answer will be equal to 1
35:13then we will check if answer is equal to
35:15nums of i
35:17so in that case frequency will be plus plus
35:19so frequency will also be 1
35:21after that we have to update our index
35:23first we will check if frequency is 0
35:25then we will check if answer is
35:27equal to nums of i
35:29if answer is equal to nums of i
35:31if answer is not equal to nums of i
35:33that means we have to make frequency minus minus
35:35frequency will become 0 after being minus minus
35:37but we don't have to change anything in answer
35:39we will go to next iteration
35:41in next iteration
35:43we will come here
35:45first we will check if frequency is equal to 0
35:47yes the frequency is equal to 0
35:49so in that case this value
35:51will become our answer
35:53because 1 has only one frequency
35:552 has another frequency
35:57so 2 looks like
35:59there are only two majority elements
36:01that's why we are resetting
36:03answer as 2
36:05and we will update its frequency
36:07by 1
36:09after that we will go to next index 1
36:11we will check for 1
36:131's frequency is not 0
36:15is answer equal to nums of i
36:17this is answer and this is nums of i
36:19so I have to make frequency minus minus
36:21frequency will become 0 after being minus minus
36:23we don't have to take any action
36:25after that we will update next
36:27now we will check if frequency is already 0
36:29yes the frequency is already 0
36:31if the frequency is already 0
36:33then we will update answer
36:35this value which is equal to 1
36:37and we can increase the frequency of 1
36:39and finally loop is complete
36:41so in last our answer has stored value
36:43equal to 1
36:45so here you must have noticed
36:47that in small part it is not necessary
36:49that majority element is stored in answer
36:51in answer 2 was also stored
36:53but because majority element 1
36:55overall there is so much frequency in entire array
36:57that it will always win
36:59and that is the logic that
37:01moore's algorithm takes into account
37:03so that's all for today
37:05I hope for pair sum we have understood
37:07both brute force and second
37:09for majority element we have understood
37:11all three approaches
37:13here in majority element question
37:15we have already been told that
37:17answer will always exist for us
37:19but in majority element question
37:21there is one more variation
37:23if any majority element does not exist
37:25then in that case
37:27return minus 1
37:29for example if we have
37:31an array 1,2,3,4
37:33if we have to find majority element in this array
37:35then no majority element exists
37:37so here moore's algorithm
37:39will return answer 4
37:41but 4 is not majority element
37:43so in the question where we are not given
37:45that answer will always exist
37:47there we have to do one more extra step
37:49in our algorithm
37:51here we have returned our answer
37:53this will be the first step
37:55in second step whatever answer is returned
37:57we count its frequency
37:59and then we check
38:01is this frequency greater than n by 2
38:03if yes then return answer
38:05if not then return minus 1
38:07so this is a small extra step
38:09which we have to do
38:11in fact if I write it quickly
38:13so this moore's algorithm
38:15we have to write as it is
38:17and here simply this step will come
38:19in the entire loop
38:21we take a count variable
38:23let's suppose count is equal to 0
38:25in the loop
38:27integer value of nums we check
38:29that if value is equal to
38:31my answer then in that case
38:33count will be plus
38:35in the last
38:37if count value is greater than n by 2
38:39then in that case we will return
38:41our answer
38:43and in else case we will return minus 1
38:45this is a simple extra step
38:47which we have to do in case
38:49we are not already given that answer will always exist
38:51so this is how the majority
38:53element or the moore's algorithm
38:55is going to work
38:57I hope that you are all having a lot of fun solving these DSA questions
38:59so if you have successfully completed
39:01today's lecture
39:03you can let me know in the comments
39:05you can also let me know in twitter
39:07link is in the description box
39:09till then keep learning and keep exploring