Majority Element II

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

Key Observation

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.

---

Brute Force Approach

For every element, count its occurrences by traversing the entire array again.

Intuition

Check each number individually and verify whether its frequency exceeds n/3.

Complexity

• Time: O(N²)
• Space: O(1)

for(int i = 0; i < n; i++) {
    int count = 0;

    for(int j = 0; j < n; j++) {
        if(nums[i] == nums[j]) count++;
    }

    if(count > n/3) {
        // add if not already present
    }
}

---

Better Approach (HashMap)

Store frequencies using a HashMap.

Intuition

Instead of counting repeatedly, count every element once and then collect elements whose frequency is greater than n/3.

Complexity

• Time: O(N)
• Space: O(N)

Map<Integer, Integer> map = new HashMap<>();

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

---

Optimal Approach (Moore's Voting Algorithm)

Intuition

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:

1. Find two potential candidates.
2. Verify their actual frequencies.

Java Code

class Solution {
    public List<Integer> 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<Integer> ans = new ArrayList<>();

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

        return ans;
    }
}

Complexity

• 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]

---

Takeaway

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.