DEV Community

Cover image for Majority Element (Leetcode)
Ankan Bhattacharya
Ankan Bhattacharya

Posted on

Majority Element (Leetcode)

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;
};
Enter fullscreen mode Exit fullscreen mode

Result

Image description

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.

Image of Stellar post

Check out Episode 1: How a Hackathon Project Became a Web3 Startup 🚀

Ever wondered what it takes to build a web3 startup from scratch? In the Stellar Dev Diaries series, we follow the journey of a team of developers building on the Stellar Network as they go from hackathon win to getting funded and launching on mainnet.

Read more

Top comments (0)

Jetbrains image

Build Secure, Ship Fast

Discover best practices to secure CI/CD without slowing down your pipeline.

Read more

👋 Kindness is contagious

Dive into this thoughtful article, cherished within the supportive DEV Community. Coders of every background are encouraged to share and grow our collective expertise.

A genuine "thank you" can brighten someone’s day—drop your appreciation in the comments below!

On DEV, sharing knowledge smooths our journey and strengthens our community bonds. Found value here? A quick thank you to the author makes a big difference.

Okay