boyer moore algorithm majority element code example

Example: Find majority element (Boyer–Moore Majority Vote Algorithm)

def majorityElement(A):
 
    # `m` stores the majority element (if present)
    m = -1
 
    # initialize counter `i` with 0
    i = 0
 
    # do for each element `A[j]` in the list
    for j in range(len(A)):
 
        # if counter `i` becomes 0
        if i == 0:
 
            # set the current candidate to `A[j]`
            m = A[j]
 
            # reset the counter to 1
            i = 1
 
        # otherwise, increment the counter if `A[j]` is a current candidate
        elif m == A[j]:
            i = i + 1
 
        # otherwise, decrement the counter if `A[j]` is a current candidate
        else:
            i = i - 1
 
    return m