Majority Element II

Source: Dev.to

Given an integer array nums, return all elements that appear more than ⌊n/3⌋ times. An element must appear more than n/3 times. This means there can be at most 2 such elements. Why? If 3 different elements each appeared more than n/3 times: n/3 + n/3 + n/3 > n which is impossible. For every element, count its occurrences by traversing the entire array again. Check each number individually and verify whether its frequency exceeds n/3. Time: O(N²)

Space: O(1)

for(int i = 0; i n/3) { // add if not already present } }

Store frequencies using a HashMap. Instead of counting repeatedly, count every element once and then collect elements whose frequency is greater than n/3. Time: O(N)

Space: O(N)

Map map = new HashMap<>();

for(int num : nums) { map.put(num, map.getOrDefault(num, 0) + 1); }

Since there can be at most 2 majority elements, we only need to track 2 candidates and their counts. Whenever we encounter three different elements, they effectively cancel each other out. After all cancellations, only the potential majority elements can survive. The algorithm works in two phases: Find two potential candidates. Verify their actual frequencies. class Solution { public List majorityElement(int[] nums) {

    int candidate1 = 0, candidate2 = 0;
    int count1 = 0, count2 = 0;

    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 {
            count1--;
            count2--;
        }
    }

    count1 = 0;
    count2 = 0;

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

    List ans = new ArrayList<>();

    if (count1 > nums.length / 3) ans.add(candidate1);
    if (count2 > nums.length / 3) ans.add(candidate2);

    return ans;
}

}

Time: O(N)

Space: O(1)

Quick Dry Run

Input: [1,2,1,3,1,2,2]

After the voting phase: candidate1 = 1 candidate2 = 2

Verification: 1 -> 3 times 2 -> 3 times

Since both frequencies are greater than 7/3 = 2: Answer = [1, 2]

A useful pattern to remember: More than n/2 times → At most 1 candidate

More than n/3 times → At most 2 candidates

More than n/k times → At most k - 1 candidates

This observation forms the foundation of the Moore’s Voting Algorithm family of problems.