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?
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.
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)
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(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
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
candidatei.e., the potential candidate to be the majority element and
- At a given index
arr[i]is equal to the candidate, then, increment
arr[i]is not equal to the candidate, then, decrement
- If the
countbecomes zero, then, the value at that index will be the new value of
countwill be set to 1.
- At the end, the value stored in
candidatewill be the majority element of the array, if exists.
- As a final check, iterate through the array and check if the frequency of the
candidatein the array is greater than
n/2or not. If yes, then that is the majority element. Otherwise, we can say that the array doesn’t have a majority element.
def majorityElement(A, N): candidate = A 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)
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.
O(n) – Linear time complexity, as we are just looping through the array elements, it takes linear time.
O(1) , no extra space is being used. Constant space complexity.
Happy Learning 🙂