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];
    }
};

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];
    }
};

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

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

Blog

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

Mayank Arora

Join Our Newsletter. No Spam, Only the good stuff.

Related