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

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
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.

Happy Learning 🙂