Array

Boyer–Moore majority vote algorithm

boyer_moore_voting_algorithm(arr: list) → int

Parameters

arr – list

Returns

int

Description

To find the majority element from the sequence, majority means the element should be present more than n/2 times the total length, n, of the sequence.

If no such element occurs, then algorithm can return any arbitrary element, and is not guaranteed that this element will be the mode or occurred maximum number of times.

Important

• Linear TIme

• Constant Space

See also

Reference : wiki

Python

def boyer_moore_voting_algorithm(arr: list) -> int:
    """
    :param arr: list
    :return: int
    """
    res = arr[0]  # Initialization
    counter = 0  # Counter

    for i in range(len(arr)):
        if counter == 0:
            res = arr[i]
            counter = 1
        elif res == arr[i]:
            counter += 1
        else:
            counter -= 1

    return res

Implementation

LeetCode

Sl No	Level	Questions	Solutions	Tags
169	Easy	Majority Element	Python