Find majority element - GFG practice solution

Given an array A of N elements. Find the majority element in the array. A majority element in an array A of size N is an element that appears more than N/2 times in the array.

 

Example 1:

Input:
N = 3 
A[] = {1,2,3} 
Output:
-1
Explanation:
Since, each element in 
{1,2,3} appears only once so there 
is no majority element.

Example 2:

Input:
N = 5 
A[] = {3,1,3,3,2} 
Output:
3
Explanation:
Since, 3 is present more
than N/2 times, so it is 
the majority element.

Your Task:
The task is to complete the function majorityElement() which returns the majority element in the array. If no majority exists, return -1.
 

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
 

Constraints:
1 ≤ N ≤ 107

0 ≤ Ai ≤ 106

Practice Here :

Majority Element | Practice | GeeksforGeeks

Solution:

class Solution{

  public:

     // Function to find majority element in the array

    // a: input array

    // size: size of input array

    int majorityElement(int a[], int size)

    {

        

        // your code here

        int k =size/2;

        unordered_map<int,int> mp;

        for(int i=0;i<size;i++)

        {

            mp[a[i]]++; //store the count of all elements here in the map

        }

        

        for(auto it : mp)

        {

            if(it.second>k) //check whose count is greater than n/2

            return it.first;

        }

        return -1;

    }

};