Majority Element | GeeksforGeeks

Explanation for the article: www.geeksforgeeks.org/majority...
This video is contributed by Harshit Jain.

[@jiechaowang5960]

why can't when we loop through the array, we have a map to keep track of each element and its count, and when the count is greater than n/2 we print out that element?

[@killaknut]

You can do that, but space complexity will be higher

[@dinakarmaurya8000]

isMajority() method can be optimized.. if(count > size/2) is in loop so calculate the size/2 out side the loop to optimize the algorightm

[@mohammadmujahid8850]

When we have find the candidate element, which is a majority element, then why we again need to ceck whether its a majority element or not?

[@utkarshjain1797]

when we find the candidate element, it means we find the element having maximum occurrence in that array. But, to become majority element its count must be greater than n/2. So, that case we have to check.... I think you understand buddy...

[@harinmehta1551]

This can also be solved using Bit Manipulation. 0. make a frequency array [32] 1. Traverse thru the array and for each element : 1.1 for(int i = 0; i < 31; i++) { if( (arr[k] & i) != 0 ) freqArray[i]++; } 2. Traverse thru frequency array and for all indicies where frequency > n/2, add 2^(index) to ans

[@dhruvakadipu]

For those who're confused, don't waste your time; here's your answer. Answer: Here "Majority" means "MORE THAN ( n / 2 )". Example: 2 2 3 2 -> Majority = 2 Example: 2 1 2 3 -> Majority = Something Else This algorithm only makes sense when it is GURANTEED that an element appears more than n/2 times. So, don't misunderstand the name of the function like I did.

[@axel9194]

Thx bro

[@shivamkansagara4929]

thanks bro

[@reyou7]

why would someone down vote this video? it is nicely explained.

[@GeeksforGeeksVideos]

Haha....thanks for the appreciation. :)

[@chandreshchitalia9341]

will this algo work in java

[@AnnoyingErrors41]

def majorityNumberMoore(A,N): majority_index, counter = 0,1 for i in range(1,N): if A[majority_index] == A[i]: counter += 1 else: counter -=1 if counter == 0: majority_index = i counter = 1 candidate = A[majority_index] seen = 0 for i in range(N): if A[i] == candidate: seen += 1 if seen > N//2: return candidate return -1 Can someone improve the run time?

[@hermesmercuriustrismegistu4841]

Thx a lot for the video!

[@onlywilddrift9506]

moores method doesn't work when majority element is greater than index 0 . example test case-4,6,2,4,5,0,2,2,2,2,2,2,2,2,2

[@niteshkumar-cv3ls]

its working bro

[@naveenojha5603]

how it is o(n)

[@wecan2729]

int majorityElement(int a[], int size) { mapmp; for(int i=0;isecond>k) { return it->first; } } return -1; }

[@joysarkar548]

sort the array and return the median

[@Yatogami1706]

What if there isn't a majority element?

[@gauravkungwani]

@@Yatogami1706 before returning check for the median if its a majority element or not

[@SuyashSoni248]

for 2,2,3,8,7,9,9,6 majority elt is 9 but it must be 2. someone plz explain.

[@GeeksforGeeksVideos]

A majority element in an array A[] of size n is an element that appears more than n/2 times . Here, there is no majority element. Neither 9 nor 2. Can you please tell us why do you think otherwise?

[@vibekdutta6539]

If the array were like 2,2,2,1,3,4,5,6,6 in this case I get 6 as the majority element why? When it should be 2

[@trglegend6287]

here majority element is the element which repeat more number of time here 2 repeat more so ans is 2

[@funwithrahulbulbul3767]

​@@trglegend6287their is no majority element since the count of 2 is < n/2

[@mahenderk2149]

It wont work for below no's : 2,2,3,8, 7,9,9

[@adeete09]

It works.There is no majority element in this array and the moore's voting algo will print none in this case

[@mahenderk2149]

yes...working...thnq

[@SuyashSoni248]

for 2,2,3,8,7,9,9,6 majority index is 5 and majority elt is 9 but it must be 2. someone plz explain

[@utkarshjain1797]

#include using namespace std; // Moore's Voting Algorithm int majority(int arr[],int n) { int i,pos,count; pos = 0; count = 1; for(i=1;i>n; int arr[n]; for(i=0;i>arr[i]; } res = majority(arr,n); if(res == -1) { cout

[@Paradise-kv7fn]

There are multiple ways to solve this questions and each approach has its trade off's between the space and time complexity. 1) Brute force with TC O(n^2) and SC O(1) 2)Sort the array and then return the middle element(median) with TC O(nlogn) and SC O(1) 3)Use a HashMap with TC O(n) and SC O(n) 4)Voting algorithm with TC O(n) and SC O(1). Now I was able to think of the first 3 approaches but how the hell can you think of the fourth approach and that too in an interview? :/

[@devanggupta9986]

In method 3 -> for (1,1,1,1,2,4,5,6,8) the programme is printing none whereas it should print 1 can any one explain why???

[@kalagaarun9638]

I've been wondering the same !!

[@gurucharan1117]

i guess cause 1 dint repeat for more than 9/2-- times

[@Noone-kl6sc]

9/2 is 4.5 So the no. Of occurrence of 1 should be 5 or more.. So ans is none

[@arjuns.3752]

First sort the array using in built function . Traverse through the sorted array and check if an element is equal to its next one If it is then count++ Else count=1 As soon as it reaches greater than half of array size,print that element and break the loop and condition=1. Lastly if condition!=1 then print "No majority element" :D Problem Java??

[@beastyt2510]

I've done exactly this thing on gfg. But it shows TLE!! Btw same way of thinking lol

[@programmingstuff4031]

check this case a[ ]={2,2,3,4,2,2,3,3} here majority element is 2 but I will return 3 as candidate .

[@nikhilnagireddy754]

the element should be present more than n/2 times then it is majority element

[@spicytuna08]

using map stl from C++ simplifies solution. #include #include using namespace std; int main(void) { //int iA[] = { 3, 3, 4, 2, 4, 4, 2, 4, 4 }; //int N = 9; int iA[] = { 3, 3, 4, 2, 4, 4, 2, 4 }; int N = 8; map mapDS; int i; bool bFound = false; float fMajority = N/2; for( i=0; i fMajority ) { cout

[@coder_1037]

but if u will submit in GOG it will be give tle!!!

[@rahulvig5298]

@@coder_1037 can you help me understand why will this give a tle? I know what a tle is, just wanna know why using maps in c++ stl would give a tle.

[@KAMALKAMAL-ig6qc]

{2,2,3,5} ke lie 5 aa raha hai candidate

[@your_dad_18]

Wrong

[@LukeThompson]

Algorithm dont work u sped

[@sysshenry]

can you explain more?