Riya Varyani's Blog

Moore Voting Algorithm

Riya Varyani's photo
Riya Varyani
·

3 min read

Suppose you are given an array of size n consisting of integers and you have to find the majority element which appears more than n/2 times.

Of course, the very first approach which will come to our mind is to sort the array and return the middle element because if an element occurs more than n/2 times, it will always occupy the middle position when the array is sorted.
But the time complexity for this approach will be O(n log n) since sorting of an array of size n take O(n log n) time.

The second approach that can come to our mind is to use hash map to count the occurrences of each element in the array and then identify the element with a value in the hash map to be more than n/2.

Although the time complexity of this approach will be O(n) the space complexity will also be O(n) as we are using a hash map.

But is there any way to find out the majority element in O(n) time and O(1) space? There is! Moore Voting Algorithm

Moore Voting Algorithm is used to find the majority element among the given elements that have more than n/2 occurrences. This algorithm works on the fact that if an element occurs more than n/2 times, it means that the remaining elements other than this would be less than n/2.

Algorithm-

  1. Initialize two variables: count and majority. Set count to 0 and majority to an arbitrary value.

  2. Iterate through the array nums:
    a. If the count is 0, assign the current element as the new majority and increment count by 1.
    b. If the current element is the same as the majority, increment count by 1.
    c. If the current element is different from the majority, decrement count by 1.

  3. After the iteration, the majority variable will hold the majority element.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int majority = 0;
        for (int num : nums) {
            if (count == 0) {
                majority = num;
            }
            if (num == majority) {
                count++;
            } else {
                count--;
            }
        }
        return majority;
    }
};

Explanation

The algorithm works based on the assumption that the majority element occurs more than n/2 times in the array. This assumption guarantees that even if the count is reset to 0 by other elements, the majority element will eventually regain the lead.

Let's consider two cases:

  1. If the majority element has more than n/2 occurrences:

    • The algorithm will ensure that the count remains positive for the majority element throughout the traversal, guaranteeing that it will be selected as the final candidate.

  2. If the majority element has exactly n/2 occurrences:

    • In this case, there will be an equal number of occurrences for the majority element and the remaining elements combined.

    • However, the majority element will still be selected as the final candidate because it will always have a lead over any other element.

In both cases, the algorithm will correctly identify the majority element.

The time complexity of Moore's Voting Algorithm is O(n) since it traverses the array once and space complexity is O(1) since it uses constant space.

Thanks for reading!

C++algorithmsDSA