# Boyer-Moore Majority Voting Algorithm

The Boyer-Moore Majority Voting Algorithm is a technique used to find the majority element in a given array or sequence of elements in linear time using constant space. The majority element is the element that appears more than half of the time in the array.

For example, let’s consider the following array:

[1, 2, 3, 2, 2, 2, 4, 2, 2]

In this array containing 9 elements, the element 2 appears 6 times, which is more than half the length of the array. Therefore, 2 is the majority element in this example.

On the other hand, consider the following array:

[1, 2, 3, 4, 5]

In this array, there is no element that appears more than half the time. Each element appears only once, so there is no majority element.

## Algorithm

The Boyer-Moore Majority Voting Algorithm works by keeping track of a potential majority element and a count. If the current element is the same as the potential majority element, the count is incremented. If the current element is different from the potential majority element, the count is decremented. If the count reaches 0, the potential majority element is updated to the current element. At the end of the algorithm, we check the count of potential majority element and if it is more than half the total number of elements, we have the majority element. Otherwise it means there is no element which is repeated more than half the number of elements in the array. Below is the implementation:

``````
def find_majority(arr):
# Initialize majority_candidate to None and count to 0
majority_candidate = None
count = 0

# Iterate through the array
for candidate in arr:
# If count is 0, set majority_candidate to the current element
if count == 0:
majority_candidate = candidate

# If the current element is the same as the majority_candidate, increment count
# Otherwise, decrement count
if candidate == majority_candidate:
count += 1
else:
count -= 1

# Initialize majority_count to 0
majority_count = 0

# Iterate through the array again
# to count the occurrences of the majority_candidate
for candidate in arr:
if candidate == majority_candidate:
majority_count += 1

# If the majority_count is greater than half the length of the array,
# print the majority element and return it
if majority_count > len(arr) / 2:
print(f"Majority element for {arr} is {majority_candidate}")
return majority_candidate

# If there's no majority element, print a message and return None
print(f"There's no Majority element for {arr}")
return None

# Let's test the majority element finding algorithm
find_majority([1, 2, 3, 2, 2, 2, 4, 2, 2])
find_majority([1, 2, 3, 4, 5])
``````

Sample Output:

``````Majority element for [1, 2, 3, 2, 2, 2, 4, 2, 2] is 2
There's no Majority element for [1, 2, 3, 4, 5]
``````

Here’s how the code works:

1. The `find_majority` function takes an array `arr` as input.
2. It initializes two variables: `majority_candidate` and `count`. `majority_candidate` is set to `None`, and `count` is set to 0.
3. The function then iterates through the array `arr`. For each element in the array:
• If `count` is 0, it sets `majority_candidate` to the current element.
• If the current element is the same as `majority_candidate`, it increments `count`.
• If the current element is different from `majority_candidate`, it decrements `count`.
4. After the first iteration, `majority_candidate` will hold the potential majority element.
5. The function then iterates through the array again to count the occurrences of `majority_candidate`.
6. If the count of `majority_candidate` is greater than half the length of the array, the function prints the majority element and returns it.
7. If there is no majority element (i.e., the count of `majority_candidate` is not greater than half the length of the array), the function prints a message and returns `None`.

## Time and Space Complexity

The time complexity of this algorithm is O(n), where n is the length of the input array, as it only requires two passes through the entire array: First pass to find out potential majority element and a second pass to confirm if it’s a majority element. The space complexity is O(1), as it only uses a constant amount of extra space.

## Intuition behind the Algorithm

Imagine that there are `2n+1` people and every one has a vote. Let’s assume that there is a winner among them who gets more than `n` votes. The worst that can happen is all the people who did not vote for the winner can get together and vote for a single opponent. In other words, in this scenario, there are `n` candidates who vote for a single person and `m+1` candidates who vote for the majority candidate.

Let’s say the majority element is `m` and all other elements are `o`. In this case the worst order of combination will be `o, m, o, m, o, m, o, m, m`.

If you dry run the algorithm for the above combination, the value of majority element will be `o` until the last but one element and the count will be zero. With the last element, the majority element is reset again as count is zero and so the final value of majority element will be `m`.

Explanation borrowed from this post

It might be difficult to understand this but it’ll get easier if you try to create different arrangements and dry run the algorithm.