Majority Element LeetCode Solution

Given an array of size n, find the majority element. The majority element is the element that appears more than [ n/2 ] times.

You may assume that the array is non-empty and the majority element always exist in the array.

Example 1:

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

Example 2:

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

Link: https://leetcode.com/problems/majority-element/

Solution using unordered_map in C++: #

class Solution { public: int majorityElement(vector& a) { unordered_map<int, int> mp; int n = a.size();

    for(int i=0;i<n;i++) {
        mp\[a\[i\]\]++;
    }
    
    for(int i=0;i<n;i++) {
        if(mp\[a\[i\]\] > (n/2)) {
            n = a\[i\];
            break;
        }
    }
    
    return n;
}

};

It has \(O(n)\) time complexity and \(O(n)\) space complexity.

Solution using the Boyer-Moore voting algorithm in C++ #

class Solution { public: int majorityElement(vector& a) { int count, candidate, n;

    n = a.size();
    
    // finding the candidate
    candidate = a\[0\];
    count = 1;
    for(int i=1;i<n;i++) {
        if(candidate != a\[i\]) {
            count--;
        }else{
            count++;
        }
        
        if(count == 0) {
            candidate = a\[i\];
            count = 1;
        }
    }
    
    // find the majority candidate
    count = 0;
    for(int i=0;i<n;i++) {
        if(a\[i\] == candidate) {
            count++;
        }
        
        if(count > (n/2)) {
            break;
        }
    }
    
    return candidate;
}

};

Time complexity is same as the previous solution but we improved the space complexity to \(O(1)\).

The algorithm is well explained here

https://youtu.be/n5QY3x_GNDg