Majority Element II

Given an integer array of size n, find all elements that appear more than ⌊n/3⌋ times.

Practice Link

Intuition#

Key observation: there can be at most 2 elements that appear more than ⌊n/3⌋ times.

If three distinct elements each appeared more than n/3 times, their combined count would exceed n — impossible.

This lets us extend the Boyer-Moore Voting Algorithm from 1 candidate (for n/2) to exactly 2 candidates (for n/3).

How Boyer-Moore generalises#

For majority element I (> n/2), we keep one candidate and cancel it against any different element — a majority element survives all cancellations.

Here we keep two candidates and cancel both against any third distinct element. Elements that appear more than n/3 times cannot be fully cancelled out no matter how many elements oppose them.

The algorithm runs in two passes:

1. Candidate selection — find the two surviving candidates using the voting logic.
2. Verification — recount both candidates in a second pass. A candidate that cleared the election but doesn't actually cross n/3 gets filtered out.

The verification pass is essential — Boyer-Moore only guarantees the true majority elements appear among the candidates, not that every candidate is a majority element. For example in [1, 2, 3], both 1 and 2 end up as candidates but neither exceeds ⌊3/3⌋ = 1.

Solution — Extended Boyer-Moore Voting#

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();

        // Initialize to two distinct sentinels so the "num != ele" guards
        // work correctly before any candidate has been set.
        int ele1 = INT_MIN, ele2 = INT_MAX;
        int cnt1 = 0, cnt2 = 0;

        // Pass 1: candidate selection
        for (int num : nums) {
            if (cnt1 == 0 && num != ele2) {
                cnt1 = 1; ele1 = num;          // elect new candidate 1
            } else if (cnt2 == 0 && num != ele1) {
                cnt2 = 1; ele2 = num;          // elect new candidate 2
            } else if (num == ele1) {
                cnt1++;                         // vote for candidate 1
            } else if (num == ele2) {
                cnt2++;                         // vote for candidate 2
            } else {
                cnt1--; cnt2--;                 // cancel both candidates
            }
        }

        // Pass 2: verify — recount actual occurrences
        cnt1 = 0; cnt2 = 0;
        for (int num : nums) {
            if (num == ele1) cnt1++;
            if (num == ele2) cnt2++;
        }

        vector<int> ans;
        if (cnt1 > n / 3) ans.push_back(ele1);
        if (cnt2 > n / 3) ans.push_back(ele2);
        return ans;
    }
};

Time Complexity: O(n) — two linear passes
Space Complexity: O(1) — only four variables

Trace through the examples#

[3, 2, 3] — expected [3]

Verification: ele1=3 appears 2 times, 2 > 3/3=1 ✓. ele2=2 appears 1 time, 1 > 1 ✗.
Output: [3] ✓

[1, 2] — expected [1, 2]

Verification: ele1=1 appears 1 time, 1 > 2/3=0 ✓. ele2=2 appears 1 time ✓.
Output: [1, 2] ✓

Common pitfalls#

1. Leaving ele1/ele2 uninitialized
On the first element, the code checks num != ele2 while ele2 holds garbage — undefined behaviour. Always initialize to two distinct sentinel values.

2. Starting the verification count at 1 instead of 0
cnt1 = 1 in the recount gives ele1 a free vote, potentially pushing a non-majority element past the n/3 threshold. Reset both to 0.

3. Skipping the verification pass
The voting phase only narrows candidates — it doesn't prove they're majority elements. Without the recount, [1, 2, 3] would incorrectly return two elements instead of none.