> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/arrays/5.majority-element.md).

# 5.Majority Element

Given an array of size n, find the majority element. The **majority element is the element** that appears **more than** `⌊ n/2 ⌋` times.

### Solution I: (Using Sorting)

```cpp
class Solution
{
public:
    int majorityElement(vector<int> &nums)
    {

        int res = -1, count = 0;
        sort(nums.begin(), nums.end());
        int i = 0;
        while (i < nums.size() - 1)
        {
            if (nums[i] == nums[i + 1])
            {
                count++;
            }
            else
            {
                if (count + 1 > (nums.size() / 2))
                {
                    res = nums[i];
                }
                count = 0;
            }
            i++;
        }

        if (count + 1 > (nums.size() / 2))
        {

            res = nums[i];
        }

        return res;
    }
};
```

**Time Complexity: O(n log(n) ) , Space Complexity: O(1)**

### **Solution II:  (Using Hashmaps)**

```cpp
class Solution
{
public:
    int majorityElement(vector<int> &nums)
    {
        int res = -1;
        unordered_map<int,int> m;
        for(int i=0;i<nums.size();i++){
            
            if(m.find(nums[i])==m.end()){
                m.insert({nums[i],1});
            }
            else{
                m[nums[i]]++;
            }
        }
        
        for(auto itr=m.begin();itr!=m.end();itr++){
            
            int count = itr->second;
            if(count> nums.size()/2){
                res = itr->first;
                break;
            }
        }
     
        return res;
        
    }
};
```

**Time Complexity: O(n) , Space Complexity: O(n)**

### **Solution III: (Optimized Solution using `Moore's Voting Algo` )**&#x20;

```cpp
class Solution
{
public:
    int majorityElement(vector<int> &nums)
    {
      
        int maj_idx = 0, count = 1;
        
        for(int i = 1;i<nums.size();i++){
            if(nums[maj_idx] == nums[i]){
                count++;
            }
            else{
                count--;
            }
            
            if(count == 0){
                maj_idx = i;
                count = 1;
            }
        }
        
        return nums[maj_idx];
    }
};
```

**Time Complexity: O(n) , Space Complexity: O(1)**