Majority Element II [Medium] — Extended Boyer-Moore Voting

Problem Statement

Given an integer array, find all elements that appear more than n/3 times. At most two such elements can exist.

Input: [3,2,3] → Output: [3]
Input: [1,1,1,3,3,2,2,2] → Output: [1,2]

Intuition

Boyer-Moore extended: maintain two candidates with counts. Two-pass: first find candidates, second verify they actually exceed n/3.

Solutions

C++

vector<int> majorityElement(vector<int>& nums) {
    int c1=0,c2=0,cnt1=0,cnt2=0;
    for (int n:nums) {
        if(n==c1) cnt1++;
        else if(n==c2) cnt2++;
        else if(cnt1==0){c1=n;cnt1=1;}
        else if(cnt2==0){c2=n;cnt2=1;}
        else{cnt1--;cnt2--;}
    }
    cnt1=cnt2=0;
    for(int n:nums){if(n==c1)cnt1++;else if(n==c2)cnt2++;}
    vector<int> res;
    if(cnt1>nums.size()/3) res.push_back(c1);
    if(cnt2>nums.size()/3) res.push_back(c2);
    return res;
}

Python

def majorityElement(nums: list[int]) -> list[int]:
    c1 = c2 = None
    cnt1 = cnt2 = 0
    for n in nums:
        if n == c1: cnt1 += 1
        elif n == c2: cnt2 += 1
        elif cnt1 == 0: c1, cnt1 = n, 1
        elif cnt2 == 0: c2, cnt2 = n, 1
        else: cnt1 -= 1; cnt2 -= 1
    threshold = len(nums) // 3
    return [c for c in (c1, c2) if c is not None and nums.count(c) > threshold]

JavaScript

var majorityElement = function(nums) {
    let c1,c2,cnt1=0,cnt2=0;
    for(const n of nums){
        if(n===c1)cnt1++;
        else if(n===c2)cnt2++;
        else if(cnt1===0){c1=n;cnt1=1;}
        else if(cnt2===0){c2=n;cnt2=1;}
        else{cnt1--;cnt2--;}
    }
    const threshold=nums.length/3;
    return [c1,c2].filter(c=>c!==undefined&&nums.filter(n=>n===c).length>threshold);
};

Complexity

Time: O(n)
Space: O(1)