Answers for "How to find majority element in a sequence of values using Boyer-Moore vote algorithm?"

How to find majority element in a sequence of values using Boyer-Moore vote algorithm?

"""
Implementation of Boyer-Moore majority
vote algorithm.
Aim is to find the element with the majority
account (called majority element) in a 
sequence of values. 
Time complexity: O(n); Space complexity: O(1)
"""


def find_majority_elt(arr):
    # Find majority candidate using algorithm
    majority_candidate = -1
    votes = 0
    for elt in arr:
        if votes == 0:
            majority_candidate = elt
            votes = 1
        else:
            if(elt == majority_candidate):
                votes += 1
            else:
                votes -= 1
    return majority_candidate


def is_majority(candidate, array):
    # Confirm that candidate is majority
    n = len(array)
    if n == 0:
        return False
    count = 0
    for elt in array:
        if elt == candidate:
            count += 1
    return count > n // 2


values = [1, 1, 1, 2, 1, 3]
majority_elt = find_majority_elt(values)
# The below prints: Majority element is: 1
if is_majority(majority_elt, values):
    print("Majority element is:", majority_elt)
else:
    print("No majority element found")