Majority Element | GeeksforGeeks

This video is contributed by Harshit Jain.

[dinakarmaurya]

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

[harinmehta]

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

[jiechaowang]

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?

[AnnoyingErrors]

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?

[mohammadmujahid]

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?

[reyou]

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

[onlywilddrift]

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

[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.

[SuyashSoni]

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

[mahenderk]

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

[Paradise-kvfn]

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? :/

[wecan]

int majorityElement(int a[], int size)
{

map<int, int>mp;
for(int i=0;i<size;i++)
{
mp[a[i]]++;
}
int k=size/2;
for(auto
{
if(it->second>k)
{
return it->first;
}
}
return -1;

}

[devanggupta]

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???

[programmingstuff]

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

[arjuns.]

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??

[KAMALKAMAL-igqc]

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

[spicytuna]

using map stl from C++ simplifies solution.
#include <iostream>
#include <map>

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<int, int> mapDS;

int i;
bool bFound = false;

float fMajority = N/2;
for( i=0; i<N; i++)
{
mapDS[iA[i]]++;
if(mapDS[iA[i]] > fMajority ) {
cout << iA[i] << " is majority" << endl;
bFound = true;
break;
}

}

if(bFound == false) cout << "No majority" << endl;

for( auto &it : mapDS ) cout << it.first << " " << it.second << endl;

return 0;
}