Finding the dominant element of a sequence (Boyer-Moore majority voting algorithm)
A couple of articles ago I already looked at one of the Boyer-Moore algorithms, with which you could find a substring in a string.
Today I want to chat about the majority vote algorithm, which allows you to find the dominant element of a sequence.
I suggest using it right away on the example of the “Majority Element” task with leetcode.
The condition is here: https://leetcode.com/problems/most-frequent-even-element/description/
By the way, I have a telegram channel where I write approaches to solving various problems with LeetCode, there are more analyses of specific problems than here, because an article is not always needed. In general, if you are interested – wait here – t.me/crushiteasy 🙂
Let's go back to Moore!
Briefly: we receive an array of numbers as input. We need to find the number that occurs the most times.
It's not super obvious, but this number takes up more than half of the array elements, i.e.
[1,1,2] – dominant element 1
[3,10,56,3] – there is no dominant element
[3,10,35,3,3] – dominant element 3
Limitations with leetcode:
In general, the problem can be solved without an algorithm using, for example, a hash table, where we will write down the element and the number of times it occurs. And then we will go through it and return the number that occurs more often.
The Java code would look like this:
public int majorityElement(int[] nums) {
Map<Integer, Integer> majorMap = new HashMap();
for (int i = 0; i < nums.length; i++) {
majorMap.put(nums[i], majorMap.getOrDefault(nums[i], 0) + 1);
}
int majorElement = 0;
int maxMajority = 0;
for (Map.Entry<Integer, Integer> entry: majorMap.entrySet()) {
int currElement = entry.getKey();
int majority = entry.getValue();
if (majority > maxMajority) {
maxMajority = majority;
majorElement = currElement;
}
}
return majorElement;
}The time complexity of such an algorithm will be O(n), since we go through the array once – O(n) and through the hash table once O(m), i.e. The overall complexity is O(n+m)~ O(n)
Space complexity: O(n), since the number of elements in the hash table will depend on the size of the input array.
What does the Boyer-Moore algorithm allow us to do in this case?
In terms of time complexity, we will not gain anything, since we will have to traverse the array in any case, i.e. it will remain equal to O(n), but the space complexity will improve to O(1), since we will only need two variables in which we will store the values of the potential dominant element and the number of times it occurs (the counter).
So, the algorithm itself.
We go through each element of the given sequence, check the counter value. If the counter is 0, then the current element becomes a potential candidate for the prevailing element (hereinafter candidate), and the counter is increased by 1. Then, if candidate is equal to the current element, the counter is increased, and if not, it is decreased.
If we are not sure that such an element exists in the sequence, we need to go through it again and make sure that the element occurs in the array more than n/2, where n is the length of the array. P.S. In the leetcode task, this is not necessary, because we are guaranteed that such an element definitely exists.
So the code:
public static int majorityElement(int[] nums) {
//Часть 1 - Находим «кандидата на большинство»
int candidate = nums[0];
int count = 1;
for (int i = 1; i < nums.length; i++) {
if (count == 0) {
candidate = nums[i];
}
count += (nums[i] == candidate) ? 1 : -1;
}
//Часть №2 - Проверяем, является ли кандидат большинством
//не нужна для leetcode
count = 0;
for (int num : nums) {
if (num == candidate) {
count++;
}
}
if (count > nums.length / 2) {
return candidate;
} else {
throw new IllegalArgumentException("No majority element found");
}
}Conclusion: the algorithm allows to reduce the space complexity to O(1), which is useful, I must say 🙂
