In this tutorial, we’ll learn about Moore’s voting algorithm in Python. To understand this, let’s start with the problem of finding the majority element in a given array.

Majority element problem

Say, you’re given an array A of size n. Now, the element in the array, that appears more than n/2 times is said to be the majority element. Can you think of ways to find this majority element for a given array?

Analysis

What can you infer from the given problem statement?

One of the most important observation to note is that, for a given array, there can be at most one majority element. This is because, for an array of size n, it is possible only for one element to occur more than n/2 times in the array. There can even be a possibility of no element to occur more than n/2 times, and in that case, the majority element doesn’t exist for the given array.

Naive approach

A simple approach will be, to iterate over each element of the array and check whether it is the majority element or not.

def majorityElement(A, N):
    
    for i in range(len(A)):
        
        count = 0
        for j in range(len(A)):
            if(A[j] == A[i]):
                count += 1

        if(count > N/2):
            return A[i]
    
    return -1


if __name__ == "__main__":
  arr = [3,1,3,1,3,5,3,3]
  res = majorityElement(arr,8)
  print(res)

Output

3

Time complexity

O(n) to check whether an element is the majority element or not. This operation is done for each array element, i.e., for n times. So, the overall time complexity is O(n2) .

Space complexity

O(1) , as no extra space is being used. Constant space complexity.

Can you think of a more efficient solution to solve this problem?

Edge cases to consider

1.  Arr = [1,1,2,2,3]
2. Arr = [1,12]

Note that in the above cases, Arr doesn’t have a majority element.

Here comes the answer to solve the problem in linear time, with Moore’s voting algorithm.

Efficient approach – Moore’s voting algorithm

• Loop through each element of the array, and maintain two integers candidate i.e., the potential candidate to be the majority element and count.
• At a given index i,
  • If arr[i] is equal to the candidate, then, increment count by 1.
  • If arr[i] is not equal to the candidate, then, decrement count by 1.
  • If the count becomes zero, then, the value at that index will be the new value of candidate and count will be set to 1.
• At the end, the value stored in candidate will be the majority element of the array, if exists.
• As a final check, iterate through the array and check if the frequency of the candidate in the array is greater than n/2 or not. If yes, then that is the majority element. Otherwise, we can say that the array doesn’t have a majority element.

Implementation

def majorityElement(A, N):
    candidate = A[0]
    count=1
    for i in range(len(A)):
        
        if(A[i]==candidate):
            count += 1;
        else:
            count -= 1;
        
        if(count == 0):
            candidate = A[i]
            count = 1
            continue
    
    res = -1
    
    #checking if the candidate is the majority or not
    count = 0
    for num in A:
        if(num == candidate):
            count += 1
    
    if(count > N/2):
        res = candidate
        
    return res


if __name__ == "__main__":
  arr = [3,1,3,1,3,5,3,3]
  res = majorityElement(arr,8)
  print(res)

Output

3

Correctness of Moore’s algorithm

Note that, for a given array, if candidate is the actual majority element i.e., the element that occurs more than n/2 times, then, the number of increments of count will be more than the number of decrements. Hence, count will remain to be greater than zero after looping through the array. Also, it is made sure that count never holds zero at the end of any iteration. So, the element stored in candidate after looping through the array is the potential majority element of the array.

Time complexity

O(n) – Linear time complexity, as we are just looping through the array elements, it takes linear time.

Space complexity

O(1) , no extra space is being used. Constant space complexity.

References:

• More on Moore’s Algorithm

Happy Learning 🙂