Boyer-Moore Majority Vote (Python)

from collections.abc import Sequence
from typing import TypeVar

T = TypeVar("T")


def majority_candidate(values: Sequence[T]) -> T | None:
    candidate: T | None = None
    balance = 0
    for value in values:
        if balance == 0:
            candidate = value
            balance = 1
        elif value == candidate:
            balance += 1
        else:
            balance -= 1
    return candidate


def majority_element(values: Sequence[T]) -> T | None:
    if not values:
        return None
    candidate = majority_candidate(values)
    if candidate is None:
        return None
    votes = sum(1 for value in values if value == candidate)
    return candidate if votes > len(values) // 2 else None


def elements_over_third(values: Sequence[T]) -> list[T]:
    if not values:
        return []
    first: T | None = None
    second: T | None = None
    count_first = 0
    count_second = 0
    for value in values:
        if first is not None and value == first:
            count_first += 1
        elif second is not None and value == second:
            count_second += 1
        elif count_first == 0:
            first, count_first = value, 1
        elif count_second == 0:
            second, count_second = value, 1
        else:
            count_first -= 1
            count_second -= 1
    limit = len(values) // 3
    return [
        item
        for item in (first, second)
        if item is not None and values.count(item) > limit
    ]


def main() -> None:
    ballots = ["ada", "bob", "ada", "ada", "cy"]
    print("winner:", majority_element(ballots))
    print("no majority:", majority_element(["a", "b"]))
    print("over a third:", elements_over_third(["x", "x", "y", "y", "z", "x"]))

    records = [
        {"team": "red"},
        {"team": "blue"},
        {"team": "red"},
        {"team": "red"},
    ]
    print("red votes:", majority_element([record["team"] for record in records]))


if __name__ == "__main__":
    main()