Problem statement – Given an unsorted array, find the majority element (element which occurs for more than N/2 times).
Clues –
- Solution must be O(N) in time and O(1) in space.
- If the majority element exists, there will only be one such element. How can we find it?
Solution – We can do this in O(N) time by the Boyer–Moore majority voting algorithm. It is a simple 3-step algorithm –
- Initialization – We will take 2 variables, ‘candidate’ and ‘votes’ and set them to 0.
- Voting – Traverse through the array once. If votes is 0, then we set candidate to the current element. We will also check, if the current element (arr[i]) is equal to the candidate, if yes, increment votes, else decrement.
- Checking the winning candidate – After Step 2, we will compute the frequency of the value in candidate. If this is more than N/2, then the candidate is the majority element, otherwise, the majority element does not exist.
So this is kind of like picking a candidate and computing how many votes he has. You may not understand it in the first glance, but try reading the logic two more times and try to write the pseudo-code for this. Believe me, this is a ridiculously simple algorithm!
Code –
// Moore's Majority Voting Algorithm procedure
// Computes the majority element in O(N) time
// Returns the majority element
// If no majority element, returns INT_MIN
int majorityElement(int arr[], int length)
{
int votes = 0, candidate = -1, i;
// Voting
for (i = 0; i < length; ++i) {
if (votes == 0) {
candidate = arr[i];
}
if (candidate == arr[i]) {
++votes;
} else {
--votes;
}
}
votes = 0;
// Get freq. of candidate
for (i = 0; i < length; ++i) { if (arr[i] == candidate) { ++votes; } } // Verify if the candidate // is the majority element if (votes > length / 2) {
return candidate;
} else {
return INT_MIN;
}
}