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)

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)

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 )

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)