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(n
^{2})
.
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

Arr
=[1,1,2,2,3]
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 andcount
.  At a given index
i
, If
arr[i]
is equal to the candidate, then, incrementcount
by 1.  If
arr[i]
is not equal to the candidate, then, decrementcount
by 1.  If the
count
becomes zero, then, the value at that index will be the new value ofcandidate
andcount
will be set to 1.
 If
 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 thann/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:
Happy Learning 🙂
Leave A Comment