Majority Element in an Array - Moore's Voting Algorithm - Amazon Interview Question

[@AnandKumar-uy7nn]

That's how one should approach any programming problem's solution!! Great Explanation maam !!

[@siddhantkumar698]

Fantastic explanation .. love from IIT KGP

[@shantanudhore4880]

[@satyaprakash4598]

Really commendable .... Low to high ... This is how logic builds.

[@prepbytes]

Thanks!

[@sachinsoma5757]

Great explanation, you made it look simple, subscribed .

[@ashutoshranjan4644]

Good explanation mam! Understand it completely

[@ayushagarwal4689]

mam, in this question after sorting mid element will be the majority element as majority element occurs more than n/2 times .so, we can write it as, in python, nums.sort() return nums[len(nums)//2]

[@hareenkumardevu4636]

Excellent explanation mam 💯 .... Thnq mam... Keep making videos

[@vivekprasad5669]

Amazing explanation

[@tarunbawari2858]

It can be solved in o(n) times by another method that we use before watching our video rather than using Moore algorithm Int b[]={0}; for(int i=0; i

[@ssquare1]

The 2nd for loop should go till max element of a[i] As it will fail for this testcase N= 4 a[i]={5,5,5,5}

[@KARTIKKUMAR-lj9lz]

here time complexity is very large. eg. let one of the element in the array is 10^1000 , then you need a array of size 10^1000. Better , you can use hashMap but that also worse case space complexity is 0(n)...

[@tarunbawari2858]

@@ssquare1 sorry bro my second loop is wrong i doesn't see at that time but instead of that you can use hashmap it will work for testcase you will give unordered_mapmp; for(int i=0; isecond>c) { cout

[@kausachan4167]

space and time tradeoff

[@nktrendings816]

Super Explanation Madam

[@lalkrishna1251]

If it is given that , majority element exists for sure , then element at majority_index will be the majority element. Because only that majority element can survive this process till end.

[@writobratabandyopadhyay721]

Very nice explanation...i have a request...please can you do a video explaining the time and space complexity...please...please...it would be a great help...😃😃

[@prepbytes]

Thanks, sure we will do it soon

[@mohitlalwani3505]

is this algo work for N/3 ?

[@aakashkatiyar5005]

leetcode se aya h?

[@siddhantkumar698]

Nope

[@amitejpratapsingh2702]

O(n) using hash map. No need to sort the array.

[@VishalSharma-hq5ti]

what if we aren't allowed to use extra space?

[@sasmitshubham9424]

take care of space complexity

[@A7503-d4i]

Loved it .. Please make videos on zco , zio , INOI & IOI

[@alphazero0]

the awesome video broke down the concepts and how to the answer very well.

[@shenth27]

It's hard to come up with this kinda algorithm during the interview. simpler solution I could think of just sort the array, maintainMaxCount and majorityElement, iterate through the array and if (arr[i-1] != arr[i]) then execute a while loop inside as long as arr[i] == arr[i+1] and count the occurance of arr[i]. if anytime the current count is larger than the maxCount, update it and also assign majority element. time complexity will be nlogn + n.

[@sarthakverma5921]

nice explanation. this can also be solved by using hashmaps

[@gokulnathnallaiya7617]

Moore tc-O(n),sc-O(1) Hash tc 0(n), sc-O(n)

[@omar-vr1kg]

using hash might take more space..if in a interview if he asks for only time complexity then yeah it will work

[@AmandeepSingh-ot6st]

One doubt ! .... If we are traversing any array twice or thrice or 4 times .... Will our time complexity still remain O(n) or it is n*O(n) ????

[@JB-ve7yh]

If we traverse the array twice, it will be 2O(n). If we traverse the array 3 times, it will be 3O(n). If we traverse the array n times, it will be n*O(n). HOWEVER, all of these are still considered O(n) runtime and therefore reduces to O(n).

[@omar-vr1kg]

actually it will be just a multiple of a constant. Since O(k*n) is same as O(n) for some small constant like 3,4 in front of n..so yeah time complexity will be O(n) only

[@deepakpal3209]

Hi can anyone take this array {2,1,1,4,2,9,2,3,5,3,2,6,3} and apply the same logic that is explained in the video. here after sorting the mid is 3 but here my question is 2 occurrence is more than 3. then how this algo is working fine.

[@rehanchoudhury1937]

You dont have any majority element here , The condition is that an element(in ur case 2) to be a majority element it must appear more then n/2 times( 2 appeared only 4 times where your n/2 is 13/2 =6.5 so we consider floor value that is 6 i.e 2 must have appeared atleast 6 times to be majority) No majority element as per question condition

[@omar-vr1kg]

This algo is only for finding majority element...like since majority element will be more than n/2 by count it will endup being as a middle element.. think it like this For every sorted array- Majority element will be middle element in all cases But middle element wont be majority element in all cases

[@AjayKumar-ju6sl]

I want to know WHY WHY WHY ?? this algorithm works .....

[@RajdeepBarman]

Try the sequence [2,3,7,7,7] starting with 2 as majority and count = 1 when we at 3 at index 1, since it's not equal to the majority (now 2), count decrements. Hence, now count = 0. Therefore, majority is now the current element 3 and count is 1 when we are at 7 at index 2, what happened in the previous step repeats. With 7 now being majority and count = 1 Coming to your question as to why this algorithm works; it's because, if you observe closely, when you are moving through the elements incrementing and decrementing count as per the algorithm the majority element (since they are more in number) will eventually set itself as the majority even if we don't start with it being the majority element. Therefore, when you are at the end it's going to be the majority. It's an extremely smart algorithm. Hats off to Robert S. Boyer and J. Strother Moore. One would have to be extremely ingenious to arrive at this algorithm, let alone in an interview

[@sairam6873]

int main(){ int arr[10]={2,2,2,2,7,7,7,3}; sort(arr,arr+10); int c=1; for(int i=0;i=4){ cout

[@abhishekshankar1136]

bro this is going to take O( nlogn ) because youre sorting , to do it in O(n) you need moore voting algo

[@ShivamJha00]

Bruh if you're sorting it anyway, then arr[n/2] is always going to be your majority element (assuming a majority element always exists)

[@uttamkarmakarece3534]

Ma'am if you can slow down a bit while teaching it would be great for every students I guess... otherwise great explaination

[@savantdude]

the explanation is garbage!