Majority Element (n/2 times)

Brute Force#

For every element, count the occurrences and find majority elements. This uses two nested loops — O(n²) time — and no extra space.

Better Solution#

Count the frequency of each element using a hash map, then scan the map for any entry whose count exceeds n/2. This reduces time to O(n) at the cost of O(n) extra space for the map.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int,int> hashMap;
        for(int num: nums){
            hashMap[num]++;
        }

        for(auto x: hashMap){
            if(x.second > n/2){
                return x.first;
            }
        }
        return -1;
    }
};

Time Complexity: O(n)

Space Complexity: O(n)

Optimal Solution#

Apply the Boyer-Moore Voting Algorithm. Maintain a candidate and a count. When count reaches 0, switch the candidate to the current element. If the current element matches the candidate, increment the count; otherwise decrement it. The intuition is that a majority element (appearing more than n/2 times) can never be fully "voted out" — it will always survive as the last standing candidate. This achieves O(n) time and O(1) space.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int n = nums.size();
        int majCount=0, majEle=-1;

        for(int i=0; i<n; i++){
            if(majCount==0){
                majCount = 1;
                majEle = nums[i];
            }else if(majEle == nums[i]){
                majCount++;
            }else{
                majCount--;
            }
        }
        return majEle;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)