Moore's Voting Algorithm - Finding the Majority Element

1. Problem Statement

Given an array of integers nums of size n, find the element that appears more than n / 2 times.

A majority element, if it exists, occurs more than half the time.

Example

Input:  nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2

The element 2 appears 4 times in an array of size 7. Since 4 > 7 / 2, it is the majority element.

2. Core Intuition

The key idea is cancellation.

• If the current element matches the candidate, increase the count.
• If it differs, decrease the count.
• If the count reaches zero, choose the current element as the new candidate.

Why does this work?

A majority element appears more than all other elements combined. Therefore, even if we pair each occurrence of the majority element with a different element, some occurrences of the majority element will remain.

3. Algorithm

Maintain two variables:

• candidate: the current potential majority element.
• count: the current voting balance.

1. If count == 0, select the current element as the candidate.
2. If the current element equals the candidate, increment count.
3. Otherwise, decrement count.
4. After processing the array, the candidate is the majority element if a majority is guaranteed to exist.

If the problem does not guarantee a majority element, perform a second pass to verify the candidate's frequency.

4. Dry Run

Consider:

nums = [2, 2, 1, 1, 1, 2, 2]

Final candidate: 2

Its actual frequency is 4, which is greater than 7 / 2. Therefore, 2 is the majority element.

5. C++ Implementation

This version assumes a majority element is guaranteed to exist, as in LeetCode 169.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int count = 0;
 
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
 
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
 
        return candidate;
    }
};

When a Majority Is Not Guaranteed

Verify the candidate before returning it.

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int count = 0;
 
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
 
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }
 
        count = 0;
 
        for (int num : nums) {
            if (num == candidate) {
                count++;
            }
        }
 
        return count > nums.size() / 2 ? candidate : -1;
    }
};

Here, -1 represents the absence of a majority element, assuming it is the required sentinel value.

6. Complexity Analysis

• Time Complexity: O(n) — one pass, or two passes when verification is required.
• Auxiliary Space: O(1) — only a constant number of variables are used.

7. Edge Cases

The last example demonstrates why verification is necessary when the problem does not guarantee a majority element.

8. Common Mistakes

• Assuming the final candidate is always the majority element.
• Forgetting to reset the candidate when count == 0.
• Confusing count == 0 with the absence of a majority element.
• Using extra space to store element frequencies when O(1) auxiliary space is sufficient.

9. Quick Revision

• Algorithm: Moore's Voting Algorithm.
• Purpose: Find an element occurring more than n / 2 times.
• Core idea: Cancel votes between different elements.
• Time Complexity: O(n).
• Auxiliary Space: O(1).
• Verification: Required when a majority element is not guaranteed.

10. Practice Problems

1. LeetCode 169 — Majority Element — implement the basic algorithm.
2. LeetCode 229 — Majority Element II — find elements appearing more than n / 3 times.
3. GeeksforGeeks — Majority Element — practise the standard problem.

Remember: Moore's Voting Algorithm identifies a candidate through cancellation; the majority guarantee or a verification pass establishes whether that candidate is actually the answer.