Day 13 Leet code series, today we will be picking the problem Majority Element (https://leetcode.com/problems/majority-element/).

Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Example 1:

Input: nums = [3,2,3]
Output: 3

Example 2:

Input: nums = [2,2,1,1,1,2,2]
Output: 2

Best solution: Moore's voting algoritm, TC: O(N) SC: O(1)

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

Hashing solution

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int>mp;
        for(int i=0;i<nums.size();i++){
            mp[nums[i]]++;
        }
        int max = INT_MIN;
        int ans;
        for(auto m: mp){
            if(max < m.second){
                max = m.second;
                ans = m.first;
            }
        }
        return ans;
    }
};