Optimizing Algorithms 1: Majority Element

Let's go over to the problem statement quickly.

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

Intuition:

Upon looking at the problem, the first thing that comes to anyone's mind is the brute force solution i.e. comparing each element of the array with the other.

int majorityElement(vector<int>& nums) {
    int n = nums.size();
    for(int i=0; i<n-1; i++){
        int count = 1;
        for(int j=i+1; j<n; j++){
            if( nums[i] == nums[j]){
                count++;
                }
        }
        if( count > n/2){
            return nums[i];
        }
    }
    return -1;
}

But this solution is not very efficient, as we are using two loops so the number of comparisons made is of complexity O(n^2).

Better solution:

We can try to reduce the number of comparisons made by using additional memory and keeping a count of each element.

int majorityElement(vector<int>& nums) {
    unordered_map<int,int> mp;
    int n = nums.size();
    for(int i=0; i<n; i++){
        mp[nums[i]]++;
        if(mp[nums[i]] > n/2){
            return nums[i];
            }
       }
   return -1;
}

This solution is certainly better than the brute force approach in terms of time complexity but it uses an additional space of complexity O(n).

Best solution:

Now that we have reduced the time complexity of the problem to O(n), let's see how can we reduce the space complexity to solve this problem more efficiently.

Concept: Boyer-Moore Majority Voting Algorithm

Let's break down the concept. This algorithm is based on the fact that if there exists a number that is present more than n/2 times in an array of size n, it will always stand out as the remaining elements would be present less than n/2 times. Meaning, that if we select an element as a candidate and if it occurs again, it will have more votes compared to elements that are present a lesser number of times than the candidate. If the candidate element is not present, we decrease its priority(votes) and when the number of votes becomes 0, means there are an equal number of votes for the remaining elements. So the candidate element cannot be the majority and hence we choose the present element as the candidate and continue the same till all the elements are finished. The final candidate would be our majority element. We check using the 2nd traversal to see whether its count is greater than N/2. If it is true, we consider it as the majority element.

int majorityElement(int a[], int size)
{
     int curr = 0;
     int count = 0;
     for(int i=0; i<size; i++){
         if(a[i] == a[curr]){
             count++;
         }else{
             count--;
        }
        if( count < 0 ){
            count = 0;
            curr = i;
       }
    }

    count = 0;

    for(int i=0; i<size; i++){
        if(a[i] == a[curr] ){
            count++;
        }
    }

    if(count > size/2){
        return a[curr];
    }else{
        return -1;
    }
}

Time Complexity: O(n)
Space Compexity: O(1)