Majority Element

Given an array, you need to find the majority element if it exists, else return “NO”. A majority element of an array of size N, is the element whose frequency of occurrence is more than N/2 times. Thus, there will be atmost only one such element. You need to solve the problem in linear time and constant space.

Sample Input: {3, 3, 4, 2, 4, 4, 2, 4, 4}
Expected Output: 4
Explanation: The frequency of occurrence of the element 4 in the array is 5 which is greater than (N/2 or 9/2).

Algorithm:

One way to solve the problem is to count the frequency of all the elements and return the element whose frequency is greater than N/2. This approach takes linear time and linear space. To solve the problem in linear time and constant space complexity, Moore’s voting algorithm can be used.

  1. The algorithm can be divided into two parts. First part is finding the candidate element which might be the majority element. The second part is to check whether the candidate element is the majority element or not.
  2. To find the candidate element, we initialize a variable ME with the first element of the array and a variable count = 1. We loop through each element and maintains the count of the current majority element.
  3. If the next element is the same as the majority element, then we increase the count by 1, else we decrease the count by 1. If the count reaches 0, then we change the ME variable to the current element and set the count variable back to 1 and continue the iteration.
  4. After the loop ends, we get the candidate majority element store in the ME variable. We then perform another iteration on the array and compute the count of the candidate element in the array. If the count is greater than N/2, where N is the number of elements in the array, we print the element else, we print “NO”, which means there is no such element.
#include <bits/stdc++.h>
using namespace std;

int helper(vector<int> nums, int n){
	int me = nums[0];
	int count=1;
	for(int i=1; i<n; i++){
		if(nums[i]==me){
			count+=1;
		}else{
			count--;
		}
		if(count==0){
			me = nums[i];
			count=1;
		}
	}
	return me;
}

int main(){
	vector<int> nums = {3, 3, 4, 2, 4, 4, 2, 4, 4};
	int ans = helper(nums, nums.size());
	int count = 0;
	for(auto i:nums){
		if(ans==i){
			count++;
		}
	}
	if(count > (int)nums.size()/2){
		cout<<ans;
	}else{
		cout<<"No";
	}
	return 0;
}

Also, check out another popular interview problem Sort an array of 0’s, 1’s and 2’s.

One comment

Leave a Reply

Your email address will not be published.