Say you are given the following problem, either in an interview or need to solve it in your everyday work:

Given an array nums of size n, return the majority element.

Example: [3,1,2,3,3,1,2,3,2,2,3,3,3], majority element is 3

Note: the majority element is the element that occurs more than half the time (> n/2 times, n = size of the array). Let’s also assume that it’s guaranteed a majority element exists.

A practical equivalent of this problem is to find the election candidate with the majority of the vote total. This could be a civic election or you are building a distributed system where each node needs to vote for a leader for replication purposes.

This is an easy to understand problem with multiple solutions.

You can sort the array. Sorting the array groups identical integers, making it easier to find integers that occur the majority of the time. Next, iterate over the sorted array, returning the integer that occurs more than n/2 times. This runs in O(n log n) time due to the array sort and uses constant O(1) (or O(n) depending on the sorting algorithm) space.

An alternative method, you can initialize a hash table (you know, trade some space for time) to track the occurrences of integers, then return the integer that occurs more than n/2 times. This runs in constant O(1) time and uses linear O(n) space (the hash table).

Now, what if I told you there was an algorithm that runs in linear O(n) time and uses constant O(1) space? This is where the Beyer Moore Voting Algorithm comes into play.

Algorithm

We’ll initialize two variables.

• candidate will store the current majority element
• counter will store how many votes that candidate has received.

Given the following array, we will iterate over the array, one element at a time.

[3,1,2,3,3,1,2,3,2,2,3,3,3]

If the counter is 0, we set the current candidate to element at index i. Index i is the index of our current element. We set counter to 1.

If the counter is not 0, we increment the counter if the the element at i is the current candidate. If it’s not, we decrement the counter.

Once we reach the end of the array, the current candidate is the majority element.

Code

function findMajorityElement(nums) {
    let counter = 0;
    let candidate;
    let n = nums.length;

    for (let i = 0; i < n; i++) {
        const num = nums[i];

        if (counter == 0) {
            candidate = num;
            counter = 1;
        } else if (candidate == num) {
            counter++;
        } else {
            counter--;
        }
    }
    return candidate;
}

That’s all there is to it. If you’d like to know more about this algorithm, check out this video on YouTube.