Boyer-Moore Voting Algorithm

An optimal algorithm used to find the majority element, an element that has at least n / 2 occurrences.

If an element has at least n / 2 occurrences, all other elements will have less than n / 2 occurrences. If we can guarantee that the items given have a majority element that shows up at least n / 2 times, we’d only need to iterate thru the items once. Otherwise, we’d need a second traversal to ensure that the proposed majority element actually shows up at least n / 2 times.

Time complexity: $O(N)$, where $N$ = number of elements Space complexity: $O(1)$

Algorithm

1. Select a candidate element. This can be initialized to 0.
2. Initialize a counter to 0. This will keep track of the count of the candidate.
3. Iterate thru the elements
   1. If the count is 0, set the current element as the candidate
   2. If the current element is equal to the candidate, increment the count by 1
   3. Otherwise decrement the count by 1
4. If we’re not sure that there is a majority element (shows up at least n / 2 times), then do a second pass thru the elements and check the count of the proposed candidate element.
5. Return the candidate element

Essentially incrementing the count will increase the priority of the winning ability of the current candidate element. Decrementing the count will decrease the priority of the winning ability of the current candidate element.