DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Mayank Arora
Mayank Arora

Posted on

169. Majority Element [Leetcode][C++]

All suggestions are welcome. Please upvote if you like it. Thank you.


Leetcode Problem Link: 169. Majority Element


Brute Force Solution : Time O(NlogN) & Auxiliary Space O(1)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // Brute Force Solution
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};


Enter fullscreen mode Exit fullscreen mode

Better Solution : Time O(N) & Auxiliary Space O(N)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // Better Solution
        map<int,int> m;
        int len=nums.size(), pos;
        for(int i=0;i<len;i++){
            m[nums[i]]++;
        if(m[nums[i]]>(len/2))
            pos=i;
        }
        return nums[pos];
    }
};

Enter fullscreen mode Exit fullscreen mode

Optimal Solution : Time O(N) & Auxiliary Space O(1)

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        // Optimal Solution
        // Boyer–Moore Majority Voting Algorithm
        int len=nums.size(), maj=nums[0], count=1;
        for(auto i=1;i<len;i++){
            if(nums[i]==maj)
                count++;
            else
                count--;
            if(count==0){
                maj=nums[i];
                count=1;
            }
        }
        return maj;
    }
};

Enter fullscreen mode Exit fullscreen mode

All suggestions are welcome. Please upvote if you like it. Thank you.

Top comments (0)

πŸ‘‹ New to DEV?

Head over to our Welcome Thread and tell us a bit about yourself!