In the realm of computer science, we often come across problems that seem simple at first glance but can be quite complex to solve efficiently. One such problem is finding the majority element in an array. The majority element is defined as an element that appears more than ⌊ n/2 ⌋ times in an array of size n.

Let’s start with a straightforward approach. We can use a HashMap to keep track of the occurrence of each number. If we find a number that appears more than n/2 times, we return it as the majority element.

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let hash ={}
    let mid = nums.length/2;
    return (()=>{
        for(let num of nums){
            let count= (hash[num]||0) + 1
            hash[num]=count
            if(count > mid){
                return num
            }
        }
    })();
};

This approach has a time complexity of O(n) and a space complexity of O(n), because we are traversing the array once and storing each element in the HashMap.

But, can we do better? Can we solve this problem with a space complexity of O(1)? Yes, we can! Enter the “Boyer-Moore Majority Vote Algorithm”.

Think of the algorithm as a political election. We start with a candidate and their vote count. Each vote either increases the candidate’s vote count (if the voter supports the candidate) or decreases it (if the voter opposes the candidate). If the candidate’s vote count drops to zero, a new candidate steps up with their vote.

Why does this ensure that the final candidate is the majority? Because:

  1. If the candidate is not the majority, the majority will team up with other non-candidate elements to vote against the candidate, leading to their downfall.
  2. If the candidate is the majority, they will support themselves, and other elements will vote against them. But, since the majority has more than half the votes, they will always win.

In other words, it’s like a battle royale where everyone is pitted against each other. If two elements are the same, they team up. If they are different, they cancel each other out. Even in the worst-case scenario, where each non-majority element eliminates one majority element, the majority will still emerge victorious.

Here’s the code implementation:

/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function(nums) {
    let candidate =nums[0];
    let voteCount = 1;
    for(let i=1;i<nums.length;i++){
        if(nums[i]===candidate){
            voteCount++;
        }else{
            voteCount--;
            if(voteCount===0){
                candidate = nums[i];
                voteCount = 1;
            }
        }
    }
    return candidate
};

The Boyer-Moore Majority Vote Algorithm is a beautiful example of how a seemingly complex problem can be solved efficiently with a clever approach. It’s a testament to the power of algorithms in computer science.