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

To solve the question click here:(https://leetcode.com/problems/majority-element/)

The

Boyer-Moore voting algorithmis 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);
}
int answer =0;
for (Map.Entry<Integer, Integer> entry : hm.entrySet())
{
if(entry.getValue()>nums.length/2)
{
answer = entry.getKey();
}
}
return answer;
}
```

(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;
}
```

## Top comments (1)

I think sorting approach is incorrect.

Example :

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

Output: 2 but should be 1