« back

Majority Element

Tags : searching, array, geeksforgeeks, cpp, medium

Problem Statement - link #

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.

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)

Examples #

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.

Constraints #

Solutions #

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 majIndex = -1;
        int majCount = 0;
        for(int i=0; i<size; i++){  // find the majority element
            if(majCount==0){
                majIndex = i;
                majCount = 1;
            }
            else if(a[i]==a[majIndex]){
                majCount++;
            }
            else{
                majCount--;
            }
        }
        majCount = 0;
        for(int i=0; i<size; i++){  // count the number of majority element
            if(a[i]==a[majIndex])
                majCount++;
        }
        if(majCount>size/2)
            return a[majIndex];
        return -1;
        
    }
};