Majority Element (Leetcode)

#leetcode #dsa #typescript #coding

Problem Statement

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.

Approach

The problem statement states that we need to find the majority element or the element that has the highest frequency in the array. But also the frequency of that element needs to be more than the half of the length of the array.

Here one of the naive approaches can be using a hashmap. Just store the frequencies in a key value pair format, and then loop over the hash map & detect the most frequent element. This approach would give a time complexity of O(n) and a space complexity of O(n).

Here kicks in a better algorithm popularly known as Boyre-Moore's Voting Algorithm. The algorithm states:

First take a candidate element and initiate a count as well.
Now the next step is to loop over the array.
While looping if the element is equal to the candidate, we increment the count by one, else we decrement the count by one.
And if at any point the count reaches 0, then we update the candidate with the current element.
Finally at the end if we want to verify, then we can count the frequency of the final candidate and check if its frequency is more than the 1/2 the length of the array.

Time Complexity of this approach is O(n) but the space complexity is O(1) which is quite an improvement.

Intuition

First let's consider an array:

[3, 3, 3, 2, 2]

Now if we start counting the elements then at the end we would be having candidate as 3 and the count as 1. This proves that if there is a majority element then at the end one element with count at least one would definitely remain as the final result as the number of that majority element is greater than half the length of the array.

Code

function majorityElement(nums: number[]): number {
    let candidate = nums[0];
    let currentCount = 0;

    for(let i=0; i<nums.length; i++){

        // * According to moore's algorithm if value at current position is equivalent to candidate, we increment the currentCount
        if(candidate === nums[i]){
            currentCount++;
        }
        //  * According to moore's algorithm if value at current position is not equivalent to candidate, we decrement the currentCount
        else {
            currentCount--;
        }

        // * If the currentCount is equal to 0 we update the candidate as the number at current position also we increment the currentCount
        if(currentCount === 0){
            candidate = nums[i];
            currentCount++;
        }
    }

    // * NOTE: According to Moore's algo, if the currentCount is less than or equal to zero, we can conclude that no majority element exists in the array.

    let candidateCount = 0;

    // * We just verify here that the count of the selected candidate is actually greater than half of length of the array.
    for(let i of nums){
        if(i === candidate) candidateCount++;
    }

    if ((candidateCount) <= (nums.length / 2)) return -1;

    return candidate;
};

Result

Conclusion

If you have gained or learned anything from the above given explanation do not forget to give a like ❤️ to the post. Follow me for more such posts and also my social handles are given in my profile, reach me out there.

DEV Community