Majority Element II

Problem Overview

Given an array, return all elements that appear more than ⌊n/3⌋ times.

Why solve this?

Generalizes the single-candidate Boyer-Moore idea from Majority Element to two candidates at once, and proves why two — never three or more — is the mathematical limit for this threshold.

Pattern Recognition

Whenever a majority-style threshold changes from more than n/2 to a smaller fraction like more than n/3, work out the maximum possible count of qualifying elements first — it bounds how many candidates the voting algorithm needs to track.

Prerequisites

• Majority Element — this problem tracks two Boyer-Moore candidates instead of one, then verifies both.

Hints

1. At most two values can each appear more than n/3 times — if three values each appeared more than n/3 times, their counts alone would exceed n, which is impossible.
2. Extend the single-candidate Boyer-Moore voting idea to track two candidates and two counters at once.
3. The voting pass alone can be wrong — always finish with a second pass that counts each candidate's real occurrences and keeps only the ones that truly exceed n/3.

Approach

At most two elements can appear more than n/3 times each, since three such elements would together need to appear more than n times — more than the array actually holds. This bounds the problem to tracking two Boyer-Moore candidates, candidate1 and candidate2, with their own counters, count1 and count2. Scanning once: if the current value matches an existing candidate, increment that candidate's counter; otherwise, if either counter is zero, replace that candidate and reset its counter to one; otherwise, decrement both counters (this cancels one occurrence of each candidate against one occurrence of something else, which is what makes the algorithm work). This voting pass only produces candidates that COULD be majority elements — it doesn't guarantee they actually cross the n/3 threshold, so a second pass recounts each candidate's true occurrences and keeps only the ones that genuinely exceed ⌊n/3⌋.

Code

class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int candidate1 = 0, candidate2 = 0;
        int count1 = 0, count2 = 0;

        for (int num : nums) {
            if (count1 > 0 && num == candidate1) {
                count1++;
            } else if (count2 > 0 && num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (num == candidate1) count1++;
            else if (num == candidate2) count2++;
        }

        List<Integer> result = new ArrayList<>();
        if (count1 > nums.length / 3) result.add(candidate1);
        if (count2 > nums.length / 3) result.add(candidate2);
        return result;
    }
}

Related Problems

• Reverse an Arrayeasy
• Second Largest Element in an Arrayeasy
• Plus Oneeasy
• Running Sum of 1d Arrayeasy