Majority Element I (Brute, Better, and Optimal Approaches)

The Majority Element problem requires finding an element in an array of size $N$ that appears strictly more than $\lfloor N / 2 \rfloor$ times. This study note covers the problem constraints, the progression from naive nested iteration to hash map tracking, and concludes with the optimal $O(N)$ time and $O(1)$ space Moore’s Voting Algorithm.

1. Problem Definition and Core Constraints

Given an array of $N$ integers, identify the element that occurs more than $\lfloor N / 2 \rfloor$ times.

Key Rules & Constraints

• Strict Inequality: The frequency must be strictly greater than $N / 2$ ($f > \lfloor N / 2 \rfloor$), not merely equal to $N / 2$.
• Odd vs. Even Lengths:
  • For $N = 7$, $N / 2 = 3$. An element must appear at least $4$ times.
  • For $N = 8$, $N / 2 = 4$. An element must appear at least $5$ times.
• Uniqueness: At most one majority element can exist in any array because two elements cannot both occupy strictly more than half the array's capacity.

Example Walkthrough

Given Array: [2, 2, 3, 3, 1, 2, 2]

• Array Length $N = 7$
• Threshold $\lfloor 7 / 2 \rfloor = 3$
• Occurrences:
  • 1 appears $1$ time
  • 3 appears $2$ times
  • 2 appears $4$ times
• Output: 2 (since $4 > 3$)

2. Brute Force Approach: Nested Frequency Counting

The most direct approach relies on checking the total count of every single element in the array individually.

Mental Model & Execution

1. Pick an element arr[i] using an outer loop.
2. Iterate through the entire array using an inner loop to compute the frequency of arr[i].
3. If the frequency count exceeds $N / 2$, immediately return arr[i].

Code Implementation (Brute Force)

#include <vector>

int majorityElementBrute(std::vector<int>& v) {
    int n = v.size();
    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (v[j] == v[i]) {
                count++;
            }
        }
        if (count > n / 2) {
            return v[i];
        }
    }
    return -1; // No majority element found
}

Complexity Analysis

• Time Complexity: $\mathcal{O}(N^2)$ due to nested scanning over the array of size $N$.
• Space Complexity: $\mathcal{O}(1)$ as no auxiliary data structures are allocated.

3. Better Approach: Hash Map Frequency Tracking

To optimize the $\mathcal{O}(N^2)$ running time, we can trade memory for time by storing element frequencies in a hash map data structure.

Algorithm Workflow

1. Declare a Hash Map where the Key is the array element and the Value is its frequency count.
2. Perform a single pass over the array to populate frequencies: map[arr[i]]++.
3. Iterate through the map entries and check if any key's frequency exceeds $N / 2$.

Code Implementation (Better Approach)

#include <vector>
#include <map>
#include <unordered_map>

int majorityElementBetter(std::vector<int>& v) {
    int n = v.size();
    std::unordered_map<int, int> mpp;

    // Step 1: Store frequencies in map
    for (int i = 0; i < n; i++) {
        mpp[v[i]]++;
    }

    // Step 2: Search for majority element in map
    for (auto it : mpp) {
        if (it.second > n / 2) {
            return it.first;
        }
    }

    return -1;
}

Complexity Analysis

• Time Complexity:
  • Using std::unordered_map: Average case $\mathcal{O}(N)$, Worst case $\mathcal{O}(N^2)$ (due to hash collisions).
  • Using std::map (Self-Balancing BST): Guaranteed $\mathcal{O}(N \log N)$.
• Space Complexity: $\mathcal{O}(N)$ in the worst case when all $N$ elements in the array are distinct.

4. The Intuition Behind Moore's Voting Algorithm

While hashing reduces search time, it uses $\mathcal{O}(N)$ extra space. Moore’s Voting Algorithm achieves $\mathcal{O}(N)$ time complexity while maintaining $\mathcal{O}(1)$ auxiliary space.

Core Intuition: Pairwise Cancellation

If an element appears strictly more than $N / 2$ times, its occurrence count is greater than the sum of all other elements combined.

Intuitive Concept: Imagine a battle royale where each element type represents a faction. Every time two different factions meet, they destroy one member from each faction. Because the majority element faction holds more than 50% of the total population, it will always be the last faction standing, regardless of the elimination order.

Example Array: [7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 5, 5, 5, 5]

Count of '5's: 9
Count of non-'5's (7s and 1s): 7

Pairwise cancellations:
(5 vs 7), (5 vs 7), (5 vs 7), (5 vs 7), (5 vs 1) ...
Since 9 > 7, the element '5' will remain after all cancellations are complete.

5. Moore's Voting Algorithm: Step-by-Step Mechanism

The algorithm operates in two primary phases: Candidate Selection and Candidate Verification.

Phase 1: Candidate Selection

1. Maintain two state variables: element (stores current candidate) and count (initialized to 0).
2. Iterate through the array:
   • If count == 0: Assign current element as candidate (element = arr[i]) and reset count = 1.
   • Else if arr[i] == element: Increment count by 1.
   • Else (arr[i] != element): Decrement count by 1.

Why Resetting count Works

When count drops to 0, it indicates that a prefix subarray of the processed elements has an equal number of candidate occurrences and non-candidate occurrences. Dropping this prefix does not remove the overall majority element from the remaining array.

6. Complete Execution Walkthrough

Let us trace Phase 1 of Moore's Voting Algorithm on the array: arr = [7, 7, 5, 7, 5, 1, 5, 7, 5, 5, 7, 7, 5, 5, 5, 5]

Final Candidate Candidate Output from Phase 1: 5

7. Mandatory Verification Phase (Handling Edge Cases)

Crucial Rule: Phase 1 guarantees that IF a majority element exists in the array, it will be selected as the candidate. However, Phase 1 does NOT guarantee that the candidate selected is actually a majority element if the array contains no majority element.

Scenario Comparison

1. Array with Majority Element: [2, 2, 1, 1, 2]
   • Candidate returned by Phase 1: 2.
   • Real Count of 2: $3$. $3 > 5/2 \implies$ Valid.
2. Array without Majority Element: [1, 2, 3, 4]
   • Candidate returned by Phase 1: 4.
   • Real Count of 4: $1$. $1 \ngtr 4/2 \implies$ Invalid.

Phase 2: Verification Steps

1. Re-iterate through the array and calculate the exact occurrence frequency of element.
2. Check if actual_count > N / 2.
   • If true: Return element.
   • If false: Return -1 (indicating no majority element exists).

Note: If the problem statement explicitly states that a majority element is guaranteed to exist in the input array, Phase 2 can be safely omitted.

8. Comparative Analysis of Approaches

9. Implementation Reference (C++ Code Evolution)

Below is the production-ready code implementing Moore's Voting Algorithm along with Phase 2 verification:

#include <iostream>
#include <vector>

int findMajorityElement(const std::vector<int>& v) {
    int n = v.size();
    int count = 0;
    int element = -1;

    // Phase 1: Apply Moore's Voting Algorithm to find candidate
    for (int i = 0; i < n; i++) {
        if (count == 0) {
            count = 1;
            element = v[i];
        } else if (v[i] == element) {
            count++;
        } else {
            count--;
        }
    }

    // Phase 2: Verification step
    int count1 = 0;
    for (int i = 0; i < n; i++) {
        if (v[i] == element) {
            count1++;
        }
    }

    if (count1 > n / 2) {
        return element;
    }

    return -1; // Majority element does not exist
}

int main() {
    std::vector<int> arr = {2, 2, 1, 1, 1, 2, 2};
    int ans = findMajorityElement(arr);
    std::cout << "The Majority Element is: " << ans << std::endl;
    return 0;
}

10. Summary and Key Takeaways

• Problem Definition: Find an element that appears strictly more than $\lfloor N / 2 \rfloor$ times.
• Brute Force Failure: Counting each element against all others takes $\mathcal{O}(N^2)$ time, which is too slow for large inputs.
• Hashing Trade-off: Using frequency maps solves the problem in $\mathcal{O}(N)$ time, but consumes $\mathcal{O}(N)$ extra memory space.
• Moore's Core Concept: Based on the principle of cancellation—since the majority element occupies $>50\%$ of the array, cancelling opposing element pairs still leaves the majority element candidate.
• State Machine: Phase 1 dynamically tracks a candidate using element and a balance counter count.
• Zero Counter Reset: Resetting count to 1 when count == 0 discards balanced sub-segments without altering the overall majority candidate outcome.
• Verification Obligation: Always execute Phase 2 (frequency re-check) unless problem constraints explicitly guarantee that a majority element exists.
• Optimal Performance: Moore’s Voting Algorithm runs in $\mathcal{O}(N)$ time and $\mathcal{O}(1)$ space.