Topics › Arrays › Hard

Majority Element-II

Hard TUF ID 23 A2ZSDE

LeetCode ↗ Java source ↗ Edit this article ↗

Jump to code: Brute Better Optimal

Problem

Given an integer array nums of length n, return every element that appears strictly more than ⌊n/3⌋ times. The follow-up asks for O(n) time and O(1) extra space. Return the answers in increasing order (the order is not specified by the problem; sorting makes the output deterministic for testing).

A quick counting argument bounds the answer size: if three distinct values each appeared more than n/3 times, together they would exceed n elements. So there are at most two answers, and that bound is what makes the constant-space solution possible.

Constraints: 1 ≤ n ≤ 5 × 10^4, values fit in a 32-bit signed integer. The code also accepts n = 0.

Example 1

nums = [3, 2, 3]
answer = [3]             // n/3 = 1; 3 appears twice

Example 2

nums = [1, 1, 1, 3, 3, 2, 2, 2]
answer = [1, 2]          // n/3 = 2; 1 and 2 appear three times each, 3 only twice

Example 3

nums = [1, 2, 3, 4]
answer = []              // n/3 = 1; nobody appears twice

Approach 1: Brute force

Intuition. For each element, count how many times it occurs by scanning the entire array, and report it if the count exceeds n/3. Two refinements keep the output clean: skip elements already reported (so duplicates are not reported twice), and stop as soon as two answers have been found, since a third is impossible.

Algorithm.

1. For each index i: if nums[i] is already in the answer, continue.
2. Count occurrences of nums[i] over the whole array.
3. If the count is > n/3, add it. If the answer now has two elements, stop.
4. Sort and return.

static List<Integer> bruteForce(int[] nums) {
    int n = nums.length;
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if (ans.contains(nums[i])) continue;      // already reported
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (nums[j] == nums[i]) count++;
        }
        if (count > n / 3) ans.add(nums[i]);
        if (ans.size() == 2) break;               // no third element can exceed n/3
    }
    Collections.sort(ans);
    return ans;
}

Complexity. Time O(n^2): up to n full scans. Space O(1) beyond the answer list, which holds at most two elements.

Approach 2: Better, frequency map

Intuition. Counting occurrences of every value is a job for a hash map. One pass increments the count of each element; the moment a count reaches n/3 + 1, that value qualifies. Because counts increase by exactly one per step, each qualifying value crosses the threshold exactly once, so it is added exactly once without any extra de-duplication.

Algorithm.

1. For each x: increment freq[x]. If the new count equals n/3 + 1, add x to the answer.
2. Sort and return.

static List<Integer> better(int[] nums) {
    int n = nums.length;
    Map<Integer, Integer> freq = new HashMap<>();
    List<Integer> ans = new ArrayList<>();
    for (int x : nums) {
        int c = freq.merge(x, 1, Integer::sum);
        if (c == n / 3 + 1) ans.add(x);           // the count crosses the threshold exactly once
    }
    Collections.sort(ans);
    return ans;
}

Complexity. Time O(n): one pass with O(1) average map operations. Space O(n) for the map in the worst case (all values distinct).

This is a fine answer when memory is not a concern. The follow-up wants to drop the map.

Approach 3: Optimal, extended Boyer-Moore voting

Intuition. The classic Boyer-Moore algorithm finds the element that appears more than n/2 times by keeping one candidate and a counter: matching elements add a vote, differing elements cancel a vote, and when the counter hits zero a new candidate takes over. The key insight is that whenever a vote is cancelled, two different elements are discarded together, and discarding pairs of different elements cannot destroy a true majority.

For the n/3 threshold, keep two candidates with two counters. An element matching a candidate adds to that candidate’s count. An element matching neither candidate, when both counters are positive, cancels one vote from each counter, effectively discarding a triple of three distinct elements. Any value with more than n/3 occurrences cannot be eliminated by discarding triples of distinct values, because it would need to be in more than n/3 triples and there are fewer than n/3 of them. So after the pass, every true answer is one of the two candidates.

The converse does not hold: a candidate that survives is not necessarily an answer (in [1, 2, 3, 4] the survivors are 4 and 2, neither of which qualifies). A second pass counts the real occurrences of the two candidates and keeps only those above the threshold.

Algorithm.

1. Pass 1, with cand1, count1, cand2, count2, for each x:
   • if count1 > 0 and x == cand1: count1++;
   • else if count2 > 0 and x == cand2: count2++;
   • else if count1 == 0: cand1 = x, count1 = 1;
   • else if count2 == 0: cand2 = x, count2 = 1;
   • else: count1--, count2--.
2. Pass 2: count real occurrences of cand1 and cand2.
3. Add each candidate whose real count exceeds n/3; sort; return.

The order of the branches matters. Checking “matches a candidate” before “a counter is zero” ensures the two candidates are always distinct: a value is only installed as cand2 after it has failed to match cand1 while count1 > 0.

static List<Integer> optimal(int[] nums) {
    int n = nums.length;
    int cand1 = 0, cand2 = 0, count1 = 0, count2 = 0;
    for (int x : nums) {
        if (count1 > 0 && x == cand1) count1++;
        else if (count2 > 0 && x == cand2) count2++;
        else if (count1 == 0) {
            cand1 = x;
            count1 = 1;
        } else if (count2 == 0) {
            cand2 = x;
            count2 = 1;
        } else {                                  // x differs from both: cancel one vote of each
            count1--;
            count2--;
        }
    }
    count1 = 0;
    count2 = 0;
    for (int x : nums) {                          // voting only yields candidates; verify their real counts
        if (x == cand1) count1++;
        else if (x == cand2) count2++;
    }
    List<Integer> ans = new ArrayList<>();
    if (count1 > n / 3) ans.add(cand1);
    if (count2 > n / 3) ans.add(cand2);
    Collections.sort(ans);
    return ans;
}

Dry run on nums = [1, 1, 1, 3, 3, 2, 2, 2]:

Verification pass: 1 occurs 3 times, 2 occurs 3 times, n/3 = 2, so both qualify. Answer [1, 2]. Notice that 3 was a candidate for a while and was replaced; the algorithm never promises that candidates stay fixed, only that true answers end up as candidates.

Complexity. Time O(n): two passes. Space O(1): four integers plus the answer list of at most two elements.

Edge cases and pitfalls

• Skipping the verification pass. The voting pass produces candidates, not answers. [1, 2, 3, 4] ends with candidates 4 and 2 and must return [].
• Default candidate collides with a real value. The candidates start as 0 with counts 0. If the array is [0, 0, 0], cand1 becomes 0 legitimately and cand2 stays 0 with a count of 0. The verification uses else if, so each 0 is counted once, for cand1 only, and cand2 is correctly rejected. Using two independent ifs there would double count and report 0 twice.
• Branch order. Testing count1 == 0 before “matches cand2” can install a value that is already cand2 as cand1, making the two candidates equal and corrupting the counts. Keep the match checks first.
• Threshold is strict. [1, 2, 3, 1, 2, 3, 1, 2, 3] has three values at exactly n/3 = 3 each; none exceeds it, so the answer is empty.
• n/3 == 0. For n ≤ 2, every element appears more than 0 times, so [1, 2] returns both. The map version handles this because the threshold n/3 + 1 is 1.
• Empty array. All three methods return an empty list; the voting version never enters either loop and the candidates’ counts stay 0.
• Negative numbers. Only equality comparisons are used, so sign is irrelevant.
• Output order. The problem accepts any order; the code sorts so that all three methods can be compared against the same expected list.

Related problems

• Majority Element-I is the single-candidate version of the same voting argument.
• Longest Consecutive Sequence in an Array is another problem where a hash-set solution is the natural “better” step.
• 3 Sum is the next problem in this section.