Boyer-Moore majority vote

Find the value that appears more than half the time, using one counter and no extra memory.

Time O(n)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

Pair off every occurrence of the candidate with one different value and cancel both. A true majority has more copies than everything else combined, so it is the one left standing.

Code

C++PythonC#

int majorityElement(const vector<int>& a) {
    int candidate = 0, count = 0;
    for (int x : a) {
        if (count == 0) candidate = x;
        count += x == candidate ? 1 : -1;
    }
    return candidate;
}

def majority_element(a: list[int]) -> int:
    candidate, count = 0, 0
    for x in a:
        if count == 0: candidate = x
        count += 1 if x == candidate else -1
    return candidate

public static int MajorityElement(int[] a) {
    int candidate = 0, count = 0;
    foreach (int x in a) {
        if (count == 0) candidate = x;
        count += x == candidate ? 1 : -1;
    }
    return candidate;
}

Tips

If a majority is not guaranteed, do a second pass to count the candidate and confirm.

In the .NET library

a.GroupBy(x => x).MaxBy(g => g.Count()).Key gives the same answer in one line, but it allocates a group per distinct value.