DEV Community

Mayank Arora
Mayank Arora

Posted on • Edited on

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

#cpp #algorithms #leetcode #programming

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.

Source: Leetcode premium solution editorial

Top comments (0)