183. Majority Element II

At most two values can each appear more than n/3 times. Track two candidates with counts; a third distinct value cancels both. A final pass confirms the real counts.

Why at most two

More than n/3 occurrences means fewer than three such values can exist. Generalise Boyer-Moore voting to two candidates:

• If the element matches a candidate, increment that count.
• Else if a count is 0, adopt the element as that candidate.
• Else decrement both counts (a distinct third value cancels a pair).

Candidates found this way are only possible winners — a second pass counts them for real and keeps those exceeding n/3.

Worked example

[1,1,1,3,3,2,2,2] (n=8, threshold 2): candidates settle on 1 and 2, both appear 3 times > 2 → [1,2].

Complexity

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

import java.util.ArrayList;
import java.util.List;

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