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;
}
``````