Tisha Agarwal

Posted on

# LeetCode: Majority Element (Boyer-Moore Majority Voting Algorithm)

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:
Input: nums = [3,2,3]
Output: 3

Example 2:
Input: nums = [2,2,1,1,1,2,2]
Output: 2

This is a EASY LEVEL question but it is very important.
It can easily be solved using two or three technics. But the main algorithm that we'll learn while solving it is Boyer-Moore Majority Voting Algorithm

The Boyer-Moore voting algorithm is one of the popular optimal algorithms which is used to find the majority element among the given elements that have more than N/ 2 occurrences. This works perfectly fine for finding the majority element which takes 2 traversals over the given elements, which works in O(N) time complexity and O(1) space complexity.

Approaches-
(1) Nested for-loop :
Time Complexity: O(N^2)
Space Complexity: O(1)

JAVA CODE:

``````public static int majorityElement(int[] nums) {

int n=nums.length;
int max=0,ele=nums[0];
for(int i=0;i<nums.length;i++)
{
int count=0;
for(int j=i;j<nums.length;j++)
{
if(nums[i]==nums[j])
count++;
}
if(count>max)
{
max=count;
ele=nums[i];
}
}
if(max>=(int)(n/2))
return ele;

return -1;
}
``````

(2) Sorting:
Time Complexity: O(NlogN)
Space Complexity: O(1)

JAVA CODE:

``````public static int majorityElement_m2(int nums[])
{
Arrays.sort(nums);
return nums[nums.length/2];
}
``````

(3) HashMap:
Time Complexity: O(N)
Space Complexity: O(N)

JAVA CODE

``````public static int majorityElement_m3(int[] nums) {

HashMap<Integer,Integer> hm=new HashMap<>();

for(int i=0;i<nums.length;i++)
{
if(hm.containsKey(nums[i]))
hm.put(nums[i] , hm.get(nums[i])+1);
else
hm.put(nums[i],1);
}
for (Map.Entry<Integer, Integer> entry : hm.entrySet())
{
if(entry.getValue()>nums.length/2)
{
}
}
}
``````

(4)Boyer-Moore Majority Voting Algorithm:
Time Complexity: O(N)
Space Complexity: O(1)

JAVA CODE

``````public static int majorityElement_m4(int[] nums) {
int ans=nums[0];
int count=1;
for(int i=1;i<nums.length;i++)
{
if(nums[i]==ans)
count++;
else
count--;

if(count==0)
{
ans=nums[i];
count=1;
}

}
return ans;

}
``````