Majority Element II (Elements Appearing > ⌊n/3⌋ Times)

An in-depth algorithmic analysis of finding all elements in an array that appear strictly more than $\lfloor n/3 \rfloor$ times. This guide breaks down the underlying mathematical bounds, moves from an $O(n^2)$ brute force approach to an $O(n)$ hash-based approach, and culminates in the optimal $O(n)$ time and $O(1)$ space solution using an extended version of Boyer-Moore's Voting Algorithm.

1. Problem Statement & Mathematical Groundwork

Given an integer array nums of size $n$, find all elements that appear strictly more than $\lfloor n/3 \rfloor$ times.

Core Definitions

• Array Size: $n$
• Target Threshold: $\lfloor n/3 \rfloor$
• Minimum Required Frequency: $\lfloor n/3 \rfloor + 1$

Concrete Example

Consider an array nums = [1, 1, 1, 3, 3, 2, 2, 2] with length $n = 8$:

• Threshold: $\lfloor 8 / 3 \rfloor = 2$
• Required Frequency: $> 2$ (meaning an element must appear at least 3 times)
• Frequencies:
  • 1 appears 3 times ($3 > 2$) $\rightarrow$ Valid
  • 2 appears 3 times ($3 > 2$) $\rightarrow$ Valid
  • 3 appears 2 times ($2 \ngtr 2$) $\rightarrow$ Invalid
• Output: [1, 2]

2. Core Mathematical Property: At Most 2 Majority Elements

Before building an algorithm, we must prove an upper bound on the size of the output array.

Proof by Contradiction

Assume that there can be 3 distinct elements ($E_1, E_2, E_3$) in an array of size $n$ that each appear strictly more than $\lfloor n/3 \rfloor$ times.

1. The minimum frequency for each element to satisfy the condition is $\lfloor n/3 \rfloor + 1$.
2. Summing the minimum required frequencies of all 3 elements gives:

3. Test with concrete values of $n$:
   • For $n = 8$:

 *Contradiction*: $9 > 8$. An array of size 8 cannot hold 9 elements.

• For $n = 9$:

 *Contradiction*: $12 > 9$. An array of size 9 cannot hold 12 elements.

Key Rule: For any array of size $n$, there can be at most 2 elements that appear strictly more than $\lfloor n/3 \rfloor$ times. The answer size will always be within the range $[0, 2]$.

3. High-Level Flow Walkthrough

The algorithm evaluates candidates through a structured pipeline:

4. Brute Force Approach: Nested Linear Scans

Intuition

Pick every distinct element in the array and run a full linear scan over the entire array to count its frequency. If the count exceeds $\lfloor n/3 \rfloor$, add it to the result list.

To avoid duplicate counting:

• Before counting an element nums[i], verify whether it is already present in our result list.
• Stop iterating early if our result list reaches its theoretical maximum size of 2.

Code Implementation (C++)

#include <vector>

using namespace std;

vector<int> majorityElementBruteForce(vector<int>& nums) {
    int n = nums.size();
    vector<int> result;

    for (int i = 0; i < n; i++) {
        // Check if nums[i] is already added to the result
        if (result.empty() || result[0] != nums[i]) {
            int count = 0;
            for (int j = 0; j < n; j++) {
                if (nums[j] == nums[i]) {
                    count++;
                }
            }
            
            if (count > n / 3) {
                result.push_back(nums[i]);
            }
        }
        
        // Early termination: At most 2 elements can qualify
        if (result.size() == 2) break;
    }

    return result;
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(n^2)$ due to the nested loop scanning the entire array for each element.
• Space Complexity: $\mathcal{O}(1)$ auxiliary space (storing at most 2 elements in the output).

5. Better Approach: Single-Pass Hash Map Optimization

Intuition

Instead of rescanning the array repeatedly, store element frequencies in a hash map.

Instead of doing two passes (one to build the map and one to check frequencies), optimize to a single pass:

1. Iterate through the array and increment map[nums[i]].
2. Check the frequency at the precise moment it is updated.
3. If map[nums[i]] == ⌊n/3⌋ + 1, add nums[i] to the result list.
4. Checking for exact equality (==) rather than greater-than (>) ensures an element is inserted into the result list exactly once without needing additional lookup checks.

Algorithm Demonstration (nums = [1, 1, 1, 3, 3, 2, 2, 2], $n = 8$, Threshold = $2 + 1 = 3$)

Code Implementation (C++)

#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

vector<int> majorityElementBetter(vector<int>& nums) {
    int n = nums.size();
    vector<int> result;
    unordered_map<int, int> mp;
    
    // Minimal frequency required to qualify
    int minThreshold = (n / 3) + 1;

    for (int i = 0; i < n; i++) {
        mp[nums[i]]++;
        
        // Add to result exactly when it reaches the threshold
        if (mp[nums[i]] == minThreshold) {
            result.push_back(nums[i]);
        }
        
        // Early stop if max possible majority elements (2) are found
        if (result.size() == 2) break;
    }

    return result;
}

Complexity Analysis

• Time Complexity:
  • Average Case: $\mathcal{O}(n)$ using std::unordered_map.
  • Worst Case: $\mathcal{O}(n^2)$ if severe hash collisions occur in std::unordered_map (can be mitigated to $\mathcal{O}(n \log n)$ using std::map).
• Space Complexity: $\mathcal{O}(n)$ to store up to $n$ unique elements in the hash map.

6. Intuition Behind Extended Boyer-Moore Voting Algorithm

To eliminate the $O(n)$ space requirement, extend Boyer-Moore’s Voting Algorithm (originally used for the $> \lfloor n/2 \rfloor$ majority problem).

The Cancellation Principle

• For $> \lfloor n/2 \rfloor$, 1 majority element dominates because it can pair up and cancel out 1 non-majority element.
• For $> \lfloor n/3 \rfloor$, up to 2 majority elements can dominate. Therefore, cancellation works in triplets: 1 instance of Element A + 1 instance of Element B + 1 instance of a distinct Element C cancel each other out.

If an element appears strictly more than $\lfloor n/3 \rfloor$ times, it cannot be fully canceled out by triplets of other distinct elements. It is guaranteed to survive as one of the two candidate variables (el1 or el2).

7. Crucial Edge Case: Preventing Candidate Collision

When extending Boyer-Moore's algorithm to 2 candidates, a critical logical flaw can occur if binding conditions are not constrained properly.

The Bug Scenario

If cnt1 == 0, we might be tempted to set el1 = nums[i]. However, what if nums[i] is already assigned to el2?

The Fix

When reassigning a candidate whose count has dropped to zero, explicitly check that the current element is not already being tracked by the other candidate:

1. cnt1 == 0 AND nums[i] != el2 $\rightarrow$ assign to el1.
2. cnt2 == 0 AND nums[i] != el1 $\rightarrow$ assign to el2.

8. Optimal Algorithm Walkthrough & Code Implementation

Complete 2-Phase Algorithm Structure

1. Phase 1 (Candidate Selection): Track two potential candidates (el1, el2) and their respective counters (cnt1, cnt2).
2. Phase 2 (Manual Verification): The candidate selection process guarantees that if majority elements exist, they will end up stored in el1 or el2. However, it does not guarantee that el1 or el2 are valid majority elements (e.g., if no element appears $> \lfloor n/3 \rfloor$ times). A second $O(n)$ pass counts their actual occurrences to verify validity.

Code Implementation (C++)

#include <vector>
#include <climits>
#include <algorithm>

using namespace std;

vector<int> majorityElementOptimal(vector<int>& nums) {
    int n = nums.size();
    
    // Phase 1: Candidate Selection (Extended Boyer-Moore Voting)
    int cnt1 = 0, cnt2 = 0;
    int el1 = INT_MIN, el2 = INT_MIN;

    for (int i = 0; i < n; i++) {
        if (cnt1 == 0 && nums[i] != el2) {
            cnt1 = 1;
            el1 = nums[i];
        } 
        else if (cnt2 == 0 && nums[i] != el1) {
            cnt2 = 1;
            el2 = nums[i];
        } 
        else if (nums[i] == el1) {
            cnt1++;
        } 
        else if (nums[i] == el2) {
            cnt2++;
        } 
        else {
            // Triplet cancellation step
            cnt1--;
            cnt2--;
        }
    }

    // Phase 2: Manual Verification Pass
    vector<int> result;
    int freq1 = 0, freq2 = 0;

    for (int i = 0; i < n; i++) {
        if (nums[i] == el1) freq1++;
        else if (nums[i] == el2) freq2++;
    }

    int minThreshold = (n / 3) + 1;
    if (freq1 >= minThreshold) result.push_back(el1);
    if (freq2 >= minThreshold) result.push_back(el2);

    // Sorting output if required by problem constraints
    sort(result.begin(), result.end());

    return result;
}

9. The Verification Pass: Why Pass 2 is Non-Negotiable

Consider the input array nums = [1, 2, 3, 4, 5, 6], where $n = 6$.

• Threshold: $\lfloor 6 / 3 \rfloor = 2$ (Elements must appear $\ge 3$ times).
• Actual Majority Elements: None (all elements appear exactly once).

Running Phase 1 Trace

1. nums[0] = 1: el1 = 1, cnt1 = 1
2. nums[1] = 2: el2 = 2, cnt2 = 1
3. nums[2] = 3: Triplet cancellation $\rightarrow$ cnt1 = 0, cnt2 = 0
4. nums[3] = 4: el1 = 4, cnt1 = 1
5. nums[4] = 5: el2 = 5, cnt2 = 1
6. nums[5] = 6: Triplet cancellation $\rightarrow$ cnt1 = 0, cnt2 = 0

At the end of Phase 1, el1 = 4 and el2 = 5.

If we returned el1 and el2 directly without Phase 2, we would incorrectly output [4, 5].

Conclusion: Phase 1 only reduces the list of all unique elements to at most 2 viable candidates. Phase 2 is mandatory to confirm if those candidates meet the $> \lfloor n/3 \rfloor$ threshold.

10. Comparative Architectural Summary

Summary and Key Takeaways

• Upper Bound Principle: An array of size $n$ can contain at most two elements that appear strictly more than $\lfloor n/3 \rfloor$ times.
• Minimum Threshold Formula: The frequency condition $count > \lfloor n/3 \rfloor$ translates to a discrete requirement of $count \ge \lfloor n/3 \rfloor + 1$.
• Hash Map Single-Pass Optimization: Instead of iterating over the map after populating it, evaluate map[element] == (n / 3) + 1 during the array traversal to collect results instantly.
• Extended Boyer-Moore Logic: Uses 2 candidate variables and 2 counters based on a 3-element cancellation model.
• Collision Prevention Rule: When setting a candidate whose counter is 0, always check that the element isn't already assigned to the other candidate (nums[i] != el2 for el1, and nums[i] != el1 for el2).
• Verification Non-Negotiable: Extended Boyer-Moore Voting identifies potential candidates; a second $O(n)$ pass is strictly required to verify whether those candidates actually cross the $\lfloor n/3 \rfloor$ threshold.