Majority Element II

medium array boyer-moore

Problem

Return every element appearing more than ⌊n/3⌋ times. There can be at most two such elements. Solve in O(n) time and O(1) extra space.

Inputnums = [3, 2, 3]

Output[3]

3 occurs twice in length 3, which is > 3/3.

nums (comma-separated)

def majorityElement(nums):
    c1 = c2 = None
    n1 = n2 = 0
    for x in nums:
        if c1 == x: n1 += 1
        elif c2 == x: n2 += 1
        elif n1 == 0: c1, n1 = x, 1
        elif n2 == 0: c2, n2 = x, 1
        else:
            n1 -= 1
            n2 -= 1
    return [c for c in {c1, c2}
            if c is not None and nums.count(c) > len(nums) // 3]

function majorityElement(nums) {
  let c1 = null, c2 = null, n1 = 0, n2 = 0;
  for (const x of nums) {
    if (c1 === x) n1++;
    else if (c2 === x) n2++;
    else if (n1 === 0) { c1 = x; n1 = 1; }
    else if (n2 === 0) { c2 = x; n2 = 1; }
    else { n1--; n2--; }
  }
  const out = [];
  for (const c of new Set([c1, c2])) {
    if (c !== null && nums.filter(v => v === c).length > nums.length / 3) out.push(c);
  }
  return out;
}

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int c1 = 0, c2 = 0, n1 = 0, n2 = 0;
        for (int x : nums) {
            if (n1 > 0 && c1 == x) n1++;
            else if (n2 > 0 && c2 == x) n2++;
            else if (n1 == 0) { c1 = x; n1 = 1; }
            else if (n2 == 0) { c2 = x; n2 = 1; }
            else { n1--; n2--; }
        }
        int k1 = 0, k2 = 0;
        for (int x : nums) { if (x == c1) k1++; else if (x == c2) k2++; }
        List<Integer> out = new ArrayList<>();
        if (k1 > nums.length / 3) out.add(c1);
        if (c2 != c1 && k2 > nums.length / 3) out.add(c2);
        return out;
    }
}

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int c1 = 0, c2 = 0, n1 = 0, n2 = 0;
        for (int x : nums) {
            if (n1 && c1 == x) n1++;
            else if (n2 && c2 == x) n2++;
            else if (!n1) { c1 = x; n1 = 1; }
            else if (!n2) { c2 = x; n2 = 1; }
            else { n1--; n2--; }
        }
        int k1 = 0, k2 = 0;
        for (int x : nums) { if (x == c1) k1++; else if (x == c2) k2++; }
        vector<int> out;
        if (k1 > (int)nums.size() / 3) out.push_back(c1);
        if (c2 != c1 && k2 > (int)nums.size() / 3) out.push_back(c2);
        return out;
    }
};

Explanation

Any value appearing more than n/3 times can have at most two such winners. This solution extends the Boyer-Moore voting idea to track two candidate slots at the same time, all in constant space.

We keep two candidates c1, c2 with vote counts n1, n2. For each value x: if it matches a candidate, bump that count; else if a slot is empty (count 0), claim it for x; otherwise x disagrees with both, so we cancel one vote from each (n1--, n2--).

The cancelling is the heart of it: a value with more than a third of the votes can never be fully cancelled out, so it must survive in a slot at the end.

Voting alone can leave false candidates, so we do a final count pass and keep only those that truly appear more than n/3 times.

Example: [1,1,1,3,3,2,2,2]. Voting settles on 1 and 2; recounting shows both appear 3 times (> 8/3 ≈ 2), so the answer is [1, 2].

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