Majority Element II

Description

Majority Element II]
Given an integer array of size n, find all elements that appear more than ⌊n / 3⌋ times.

Example 1:
Input: nums = [3,2,3]
Output: [3]

Example 2:
Input: nums = [1]
Output: [1]

Example 3:
Input: nums = [1,2]
Output: [1,2]

Constraints:

1 <= nums.length <= 5 * 104
-109 <= nums[i] <= 109

Follow up: Could you solve the problem in linear time and in O(1) space?

Method 1: Brute Force

Intuition

Elements appearing more than n/3 times are rare. There can be at most two such elements. For each unique element, we count its occurrences and check if it exceeds n/3. We use a set to avoid adding duplicates to the result.

Algorithm

For each element num in the array:
- Count how many times num appears.
- If the count exceeds n / 3, add it to the result set.
Convert the set to a list and return.

public class Solution {
    public List<Integer> majorityElement(int[] nums) {
        Set<Integer> res = new HashSet<>();
        for (int num : nums) {
            int count = 0;
            for (int i : nums) {
                if (i == num) count++;
            }
            if (count > nums.length / 3) {
                res.add(num);
            }
        }
        return new ArrayList<>(res);
    }
}

Time & Space Complexity

Time complexity: $O (n^{2})$
Space complexity: $O (1)$ since output array size will be at most 22.

Method 2: Optimal (Boyer-Moore Voting Algorithm)

Concept (The 2-Chair Election):

Set up 2 podiums/chairs to track up to 2 potential candidates.
Every time a 3rd distinct element arrives and both chairs are occupied, a 3-way clash occurs (count1-- and count2--).
Since a valid candidate appears $> n /3$ times, it is mathematically impossible to eliminate all of their occurrences through 3-way clashes.
Time Complexity: $O (n)$
Space Complexity: $O (1)$
We set count to 1 in both problems reason being when we reset candidate we need to start with first vote, the reason it is not obvious in previous problem because the next line for count sets it to 1 immediately and is not a explicit initialization like here.

import java.util.*;
 
class Solution {
    public List<Integer> majorityElement(int[] nums) {
        int candidate1 = 0, count1 = 0;
        int candidate2 = 0, count2 = 0;
 
        // Pass 1: Find up to 2 potential candidates
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                candidate2 = num;
                count2 = 1;
            } else {
                // 3-way clash: 1 supporter from Chair 1, 1 from Chair 2, and incoming voter all cancel out
                count1--;
                count2--;
            }
        }
 
        // Pass 2: Verify candidates (since > n/3 majority isn't guaranteed to exist)
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (num == candidate1) count1++;
            else if (num == candidate2) count2++;
        }
 
        List<Integer> result = new ArrayList<>();
        int threshold = nums.length / 3;
        if (count1 > threshold) 
	        result.add(candidate1);
        if (count2 > threshold) 
	        result.add(candidate2);
 
        return result;
    }
}

In Phase 1, the algorithm only identifies survivors of the 3-way clashes—it does not prove that those survivors actually appeared more than $⌊ n /3 ⌋$ times.

Here are the 2 key reasons why Phase 2 is mandatory:

1. Late Arrivals Can Steal Empty Chairs

In Phase 1, whenever a chair becomes vacant (count == 0), the very next number to walk in gets to sit down. That number might only appear once in the entire array, but if it arrives right after a 3-way clash clears a chair, it sits down and survives until the end.

Example: nums = [1, 2, 3, 4] ( $n = 4$ , threshold $> 1$ )

Step 1 (1): cand1 = 1, count1 = 1
Step 2 (2): cand2 = 2, count2 = 1
Step 3 (3): 3-way clash! (1, 2, and 3 cancel). count1 and count2 drop to 0.
Step 4 (4): Chair 1 is empty, so cand1 = 4, count1 = 1.

End of Phase 1: cand1 = 4, cand2 = 2.
If you stopped at Phase 1, the program would output [4, 2]. But 4 only appears 1 time and 2 only appears 1 time—neither passes the threshold ( $> 1$ ). The true answer is [].

2. A Majority Element Might Not Exist

For Majority Element I ( $> n /2$ ), many problem variations guarantee that a majority element exists.
However, for Majority Element II ( $> n /3$ ), an array might have no valid majority elements at all (e.g., [1, 2, 3, 4, 5, 6]). Even when no element passes the threshold, Phase 1 will always leave up to two leftover numbers sitting in candidate1 and candidate2.

Summary

Phase 1 (Filter): Guarantees that if a number appears $> n /3$ times, it will be in candidate1 or candidate2.
Phase 2 (Verifier): Counts the exact frequencies of those 2 candidates to verify if they actually pass the threshold.

Obsidian Notes

Explorer