Majority Element II (LeetCode 229)

Problem Statement

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

Return the elements in any order.

Constraints

• 1 <= nums.length <= 5 × 10⁴
• -10⁹ <= nums[i] <= 10⁹

Important Note

There can be at most two elements in the array that appear more than ⌊n/3⌋ times.

Examples

Example 1

Input

nums = [3, 2, 3]

Output

[3]

Explanation

The array size is 3, so:

⌊3/3⌋ = 1

Element 3 appears 2 times, which is greater than 1.

Example 2

Input

nums = [1]

Output

[1]

Explanation

The array size is 1, so:

⌊1/3⌋ = 0

Element 1 appears once, which is greater than 0.

Example 3

Input

nums = [1, 2]

Output

[1, 2]

Explanation

The array size is 2, so:

⌊2/3⌋ = 0

Both elements appear more than 0 times.

Naive Approach

Intuition

The simplest way to solve this problem is to check the frequency of every element individually.

For each element in the array, traverse the entire array and count how many times it appears. If its frequency is greater than ⌊n/3⌋, add it to the result.

Since there can be at most two majority elements, we can stop once we find two valid elements.

Algorithm

1. Traverse each element of the array.
2. For every element, count its occurrences using another loop.
3. If the frequency is greater than ⌊n/3⌋, add it to the result.
4. Avoid inserting duplicate majority elements.
5. Return the final result.

Code

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        int n = nums.size();
        vector<int> result;

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

            int count = 0;

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

            // Check if frequency is greater than n/3
            if (count > n / 3) {

                bool alreadyPresent = false;

                // Avoid duplicates in result
                for (int num : result) {
                    if (num == nums[i]) {
                        alreadyPresent = true;
                        break;
                    }
                }

                if (!alreadyPresent) {
                    result.push_back(nums[i]);
                }
            }

            // At most two majority elements can exist
            if (result.size() == 2) {
                break;
            }
        }

        sort(result.begin(), result.end());
        return result;
    }
};

Complexity Analysis

Time Complexity

• Outer loop runs n times.
• Inner loop runs n times for each element.

Time Complexity: O(n²)

Space Complexity

• No extra data structure is used except the result array.

Space Complexity: O(1)

Why can there be at most 2 majority elements?

An element must appear more than ⌊n/3⌋ times.

If there were 3 such elements, then the total count would exceed n:

(n/3 + 1) + (n/3 + 1) + (n/3 + 1) > n

which is impossible.

Therefore, there can be at most two majority elements.

Optimal Approach: Boyer-Moore

Voting Algorithm

Optimal Approach: Boyer-Moore Voting Algorithm

Key Observation

For an element to be considered a majority element in this problem, its frequency must be greater than ⌊n/3⌋.

There can be at most two majority elements in the array. This is because if three different elements each appeared more than ⌊n/3⌋ times, their total frequency would exceed n, which is impossible.

Therefore, instead of tracking all elements, we only need to track:

• Candidate 1
• Candidate 2
• Count 1
• Count 2

Intuition

The Boyer-Moore Voting Algorithm is based on the idea of cancellation.

Consider the array:

[2, 2, 2, 1, 1, 1, 3]

The majority elements are 2 and 1.

If we remove one occurrence each of:

• 2
• 1
• 3

The remaining array becomes:

[2, 2, 1, 1]

The majority elements remain unchanged.

This means that whenever we encounter a third distinct element, we can safely reduce the counts of both current candidates. This process gradually eliminates non-majority elements while preserving potential majority candidates.

Candidate Selection Rules

For every element in the array:

Case 1: Element matches Candidate 1

Increase Count 1.

Case 2: Element matches Candidate 2

Increase Count 2.

Case 3: Count 1 is 0

Assign the current element as Candidate 1 and set Count 1 to 1.

Case 4: Count 2 is 0

Assign the current element as Candidate 2 and set Count 2 to 1.

Case 5: Element matches neither candidate

Decrease both Count 1 and Count 2.

This is known as the cancellation step.

First Pass: Finding Potential Candidates

The first traversal of the array is used to identify two potential majority elements.

At the end of this pass:

• Candidate 1 stores a potential majority element.
• Candidate 2 stores another potential majority element.

These candidates are not guaranteed to be majority elements.

Why Do We Need a Second Pass?

Consider the array:

[1, 2, 3, 4]

The algorithm may still end up with two candidates after the first pass. However, none of them actually appear more than ⌊n/3⌋ times.

Therefore, we must verify the frequencies of the selected candidates.

Second Pass: Verification

Traverse the array again and count the actual frequencies of Candidate 1 and Candidate 2.

If a candidate appears more than ⌊n/3⌋ times, add it to the answer.

Otherwise, ignore it.

Algorithm

1. Initialize two candidates and two counters.
2. Traverse the array and update candidates using the selection rules.
3. After the first pass, obtain two potential majority candidates.
4. Traverse the array again and count the frequencies of these candidates.
5. Add candidates whose frequency is greater than ⌊n/3⌋ to the result.
6. Return the result.

class Solution {
public:
    vector<int> majorityElement(vector<int>& nums) {
        
        int candidate1 = -1, candidate2 = -1;
        int count1 = 0, count2 = 0;

        // First Pass: Find 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 {
                count1--;
                count2--;
            }
        }

        // Second Pass: Verify candidates
        count1 = 0;
        count2 = 0;

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

        vector<int> result;

        if (count1 > nums.size() / 3) {
            result.push_back(candidate1);
        }

        if (count2 > nums.size() / 3) {
            result.push_back(candidate2);
        }

        return result;
    }
};

Complexity Analysis

Time Complexity

O(n)

• First pass to find candidates.
• Second pass to verify frequencies.

Space Complexity

O(1)

Only two candidates and two counters are maintained throughout the algorithm.

problem link:

Majority Element II - LeetCode

Video references:

https://youtu.be/vwZj1K0e9U8?si=2WTqpV3IEF5XBijv