Majority Element and Boyer–Moore Voting

EditorialUpdated Oct 25, 2026

More than half

A hall is full of people holding signs. Ask any two people whose signs differ to leave together, and keep doing it until everyone still standing holds the same sign. If one sign was held by more than half the hall, its holders are the ones still standing, whatever order the pairs left in.

That's the whole idea behind Majority Element: return the value that appears more than n/2 times (the problem promises there is one). The direct ways all cost something:

count each value with a scan: O(n²), 10,000,000,000 steps at n = 100,000;
count with a hash map: O(n) time, but O(n) extra space;
sort, and take the middle value: a value that fills more than half the slots must cover the middle one. majority_by_sorting([2, 2, 1, 1, 1, 2, 2]) sorted it to [1, 1, 1, 2, 2, 2, 2] and returned 2. That's O(n log n).

Cancelling pairs gets it in one pass with two variables.

The values 2, 2, 1, 1, 1, 2, 2. Three pairs of different values, each a 2 with a 1, are joined and crossed out; one 2 is left standing. A note says each pair removes at most one 2, and there are only three other values to pair the four 2s with. Below, 1 2 1 2, exactly half 1s, cancels away completely.

Why cancelling never loses the majority

Say v fills more than half of the n values, c of them with c > n/2. Remove two values that differ. At most one of them is a v, so v drops to at least c − 1 while the total drops to n − 2, and c − 1 > (n − 2)/2: v still fills more than half of what's left. Keep going until no two different values remain. What's left is all one value, it isn't empty (v is more than half of it), so it's all v.

Try to break it below. Pair any two different values, as many times as you like, and try to wipe out the 2s. Then switch to exactly half and no majority to see when cancelling can lose.

Cancel Pairs: cancel two different values at a time, and try to wipe out the majority

Exactly half isn't enough: in 1 2 1 2, every 1 can be paired with a 2. And with no majority at all, something may still survive, but it's only a candidate. That's why a check comes later.

Boyer–Moore: one candidate and a count

Boyer–Moore voting is the cancelling game played in reading order. Keep a candidate and a count, the number of the candidate's copies still waiting for a partner. Each value does one of three things:

nothing is waiting (count 0): it becomes the candidate, and waits;
it equals the candidate: it waits too, count + 1;
it differs: it pairs off with one waiting copy, and both leave, count − 1.

The waiting copies are always copies of one value, so a number is enough to remember them. Every pair that leaves is two different values, so by the argument above the majority is what's waiting at the end. Switch the widget to Boyer–Moore's pairing to watch it pick its pairs.

Boyer–Moore on [2, 2, 1, 1, 1, 2, 2] — The current value is indigo; the amber cells are the candidate's copies still waiting.

int majorityElement(const vector<int>& nums) {
    int candidate = 0, count = 0;                 // count: the candidate's copies still waiting for a partner
    for (int x : nums) {
        if (count == 0) candidate = x;            // nothing waiting: x starts a new group
        count += (x == candidate) ? 1 : -1;       // the same value waits; a different one cancels one copy
    }
    return candidate;                             // a majority is promised, so the survivor is it
}

def majority_element(nums):
    candidate, count = None, 0                  # count: the candidate's copies still waiting for a partner
    for x in nums:
        if count == 0:
            candidate = x                       # nothing waiting: x starts a new group
        count += 1 if x == candidate else -1    # the same value waits; a different one cancels one copy
    return candidate                            # a majority is promised, so the survivor is it

static int majorityElement(int[] nums) {
    int candidate = 0, count = 0;                 // count: the candidate's copies still waiting for a partner
    for (int x : nums) {
        if (count == 0) candidate = x;            // nothing waiting: x starts a new group
        count += (x == candidate) ? 1 : -1;       // the same value waits; a different one cancels one copy
    }
    return candidate;                             // a majority is promised, so the survivor is it
}

function majorityElement(nums) {
    let candidate = 0, count = 0;                 // count: the candidate's copies still waiting for a partner
    for (const x of nums) {
        if (count === 0) candidate = x;           // nothing waiting: x starts a new group
        count += (x === candidate) ? 1 : -1;      // the same value waits; a different one cancels one copy
    }
    return candidate;                             // a majority is promised, so the survivor is it
}

Each prints 3, 2, 1, 5, 2 and −1 for [3, 2, 3], [2, 2, 1, 1, 1, 2, 2], [1], [6, 5, 5], [1, 1, 2, 2, 2] and [-1, -1, 4]. One pass, two variables: O(n) time, O(1) space.

When a majority isn't promised, count again. If nothing fills more than half, the survivor is just the last value standing. A second pass decides:

def majority_or_none(nums):
    candidate, count = None, 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    if 2 * nums.count(candidate) > len(nums):  # the second pass: is the survivor really more than half?
        return candidate
    return None

It returned 2, None and None for [2, 2, 1, 1, 1, 2, 2], [1, 2, 3] and [1, 2, 1, 2]. Still O(n) time and O(1) space.

More than a third: two candidates

Majority Element II wants every value that appears more than n/3 times. There can be at most two: three of them would add up to more than n.

A strip of 9 slots, a third being 3. Two values with 4 copies each fill 8 slots. A third value above a third would need 4 more slots, and only 1 is left.

So keep two candidates, each with its own count, and cancel three different values at a time: a value above n/3 loses at most one copy per three removed, so it survives. For each value, in this order:

it matches candidate a, or candidate b: that count goes up;
a count is 0: the value takes that place;
otherwise it differs from both, and x, one a and one b cancel: both counts go down.

The order matters. Check both candidates before taking an empty count, or a value can take one place while it already holds the other. And the second pass isn't optional here: a candidate can survive without being above a third.

Two candidates on [1, 2, 1, 3, 1, 2, 2] — The current value is indigo; the variables show both candidates and their counts.

vector<int> majorityElementII(const vector<int>& nums) {
    int a = 0, b = 1, countA = 0, countB = 0;     // two candidates (different to start) and their waiting copies
    for (int x : nums) {
        if (x == a) countA++;
        else if (x == b) countB++;                // match both candidates before taking an empty count
        else if (countA == 0) { a = x; countA = 1; }
        else if (countB == 0) { b = x; countB = 1; }
        else { countA--; countB--; }              // x and one copy of each: three different values cancel
    }
    vector<int> out;
    for (int c : {a, b}) {                        // the second pass: survivors are only candidates
        int seen = 0;
        for (int x : nums) seen += (x == c);
        if (3 * seen > (int)nums.size()) out.push_back(c);
    }
    return out;
}

def majority_element_ii(nums):
    a, b, count_a, count_b = None, None, 0, 0   # two candidates and their waiting copies
    for x in nums:
        if x == a:
            count_a += 1
        elif x == b:                            # match both candidates before taking an empty count
            count_b += 1
        elif count_a == 0:
            a, count_a = x, 1
        elif count_b == 0:
            b, count_b = x, 1
        else:                                   # x and one copy of each: three different values cancel
            count_a -= 1
            count_b -= 1
    return [c for c in (a, b) if c is not None and 3 * nums.count(c) > len(nums)]   # the second pass

static List<Integer> majorityElementII(int[] nums) {
    int a = 0, b = 1, countA = 0, countB = 0;     // two candidates (different to start) and their waiting copies
    for (int x : nums) {
        if (x == a) countA++;
        else if (x == b) countB++;                // match both candidates before taking an empty count
        else if (countA == 0) { a = x; countA = 1; }
        else if (countB == 0) { b = x; countB = 1; }
        else { countA--; countB--; }              // x and one copy of each: three different values cancel
    }
    List<Integer> out = new ArrayList<>();
    for (int c : new int[]{a, b}) {               // the second pass: survivors are only candidates
        int seen = 0;
        for (int x : nums) if (x == c) seen++;
        if (3 * seen > nums.length) out.add(c);
    }
    return out;
}

function majorityElementII(nums) {
    let a = 0, b = 1, countA = 0, countB = 0;     // two candidates (different to start) and their waiting copies
    for (const x of nums) {
        if (x === a) countA++;
        else if (x === b) countB++;               // match both candidates before taking an empty count
        else if (countA === 0) { a = x; countA = 1; }
        else if (countB === 0) { b = x; countB = 1; }
        else { countA--; countB--; }              // x and one copy of each: three different values cancel
    }
    return [a, b].filter((c) => 3 * nums.filter((x) => x === c).length > nums.length);   // the second pass
}

Each prints [3], [1], [1, 2], [1, 2], [], [2] and [4] for [3, 2, 3], [1], [1, 2], [1, 2, 1, 3, 1, 2, 2], [1, 1, 2, 2, 3, 3], [2, 2] and [4, 4, 4, 1, 2, 3]. Two passes, four variables: O(n) time, O(1) space.

The same idea scales: values above n/k number at most k − 1, so k − 1 candidates and counts, cancelling k different values at a time, find them in one pass plus a check. That's the Misra–Gries algorithm, used to find the heavy hitters in a stream too big to store.

Spotting it

Clues for Boyer–Moore:

"more than half", "more than n/3", "more than n/k";
O(1) extra space, or the values arrive as a stream;
the answer is a value, not where it is.

And the near-misses:

the most frequent value (the mode), with no "more than half": Boyer–Moore's survivor may not be it. Count with a hash map (Hashing).
the top k most frequent values: a hash map, then a heap or bucket sort (Heaps & Priority Queues).
a majority in a range of the array, asked many times: that's a data-structure problem, beyond one pass.

Common mistakes

Skipping the first value's vote. candidate, count = nums[0], 0 and then for x in nums[1:]

The first value is never counted, so the first different value takes over: [3, 2, 3] returned 2. Start with nothing waiting and read every value.

Trusting the survivor when a majority isn't promised.

Without the second pass, [1, 2, 3] returned 3, which appears once. Count the candidate before answering.

Taking an empty count before checking the other candidate. elif count_a == 0: above elif x == b:

A value can then hold both places. The shortest failing array of 1s, 2s and 3s is [1, 2, 3, 2]: the candidates ended as [2, 2], and the answer came out [2, 2] instead of [2]. Check both candidates first.

>= instead of > in the check.

[1, 1, 2, 2, 3, 3] has nothing above a third (each appears exactly n/3 times), but it returned [1, 2]. More than a third means 3 * count > n.

Check yourself

Quiz

1 / 6

Multiple choice

Seven values, and 2 appears four times. You cancel pairs of different values in any order until no pair is left. What's left?

Practice problems

From easier to harder:

Majority Element: one candidate and a count; the majority is promised.
Majority Element II: two candidates, the order of the checks, and the second pass.

That's the Arrays section. The Arrays Quiz checks all four lessons.