Daily bit(e) of C++ | Majority element
Daily bit(e) of C++ #268, Common C++ interview problem: Majority element.
Today, we will look at a common C++ interview problem: Majority element.
Given an array of integers as std::vector<int>, return the majority element (guaranteed to be present).
A majority element has more than size/2 number of instances in the array.
For example, in the array {1,0,1,1,0,1,0}, the majority element is 1 with 4 instances, and the element 0 has only 3 instances.
There is a solution that runs in O(n) time and O(1) space.
Before you continue reading the solution, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/nvvcPTen1.
Solution
There are a few ways to implement an O(n) solution, for example, by keeping track of value frequencies. However, a solution that maintains O(1) space complexity is tricky.
A common thread between optimal solutions when looking for a very specific element is that we need to properly understand and exploit the properties of the element we are looking for. What exactly does it mean for an element to have the majority?
Notably, we can pair up each instance of the element with another element in the array, and we will still have leftover instances.
This means that we can easily verify whether an element has a majority by simply keeping track of a counter:
if the current element is not the candidate, decrease the counter
if the current element is the candidate, increase the counter
What would happen if we ran this algorithm with the wrong candidate?
We are guaranteed to end up with a negative number. However, a more useful fact is that whenever our counter reaches zero, we have evidence that the candidate isn’t a majority element in the current prefix.
This gives us the Boyer–Moore majority vote algorithm. Run the above algorithm with the following additional step:
if the counter is zero, increase it to one and switch the candidate to the current element
This way, we effectively chop the array into segments with perfectly paired elements. And since our majority element will still have leftover instances even after pairing up with everything else in the array, at some point, it will become the candidate and the counter will remain positive.
