Moore’s Majority Vote Algorithm: Find Majority Element Explained with Examples

Moore’s Majority Vote Algorithm is a clever algorithm used to find the majority element in a sequence of numbers in O(n) time and O(1) space. The majority element is defined as the element that appears more than n/2 times in an array of n elements.

In this article, we will explore:

• What majority element means
• Detailed working of Moore’s Majority Vote Algorithm
• Step-by-step visualization with diagrams
• Python implementation with examples
• Complexity analysis and limitations

Understanding Majority Element

Imagine you have an array where one number occurs more frequently than all the others combined. That number is the majority element. For example:

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

The element 2 is the majority because it occurs 4 times in an array of 7 elements, which is greater than 7/2 = 3.

Idea Behind Moore’s Majority Vote Algorithm

The algorithm was proposed by Robert S. Moore and is based on the idea of vote cancellation. Every element tries to represent a “vote”. If there is a majority element, all other elements cannot cancel it out completely — it will still remain after all cancellations.

Algorithm Steps

1. Initialize two variables: candidate and count as 0.
2. Traverse the array:
   • If count is 0, set candidate to the current element.
   • If the current element equals candidate, increment count.
   • Otherwise, decrement count.
3. After traversing the entire array, candidate will hold the potential majority element.
4. Verify whether candidate is actually a majority (since the algorithm assumes existence of majority).

Python Implementation

def majority_element(nums):
    # Phase 1: Find candidate
    count = 0
    candidate = None
    
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    
    # Phase 2: Verify candidate
    if nums.count(candidate) > len(nums) // 2:
        return candidate
    return None

# Example Usage
print(majority_element([2, 2, 1, 1, 1, 2, 2]))  # Output: 2
print(majority_element([3, 3, 4, 2, 4, 4]))     # Output: None (no majority)

Step-by-Step Example

Let’s walk through the array [2, 2, 1, 1, 1, 2, 2].

At the end, candidate=2, which passes verification as the majority.

Interactive Example

Try running this small interactive simulation in Python yourself:

def simulate(nums):
    count = 0
    candidate = None
    print("Step | Num | Candidate | Count")
    print("------------------------------")
    for i, num in enumerate(nums):
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
        print(f"{i+1:4} | {num:3} | {candidate:9} | {count:5}")
    return candidate

simulate([2, 2, 1, 1, 1, 2, 2])

Complexity Analysis

• Time Complexity: O(n), since we traverse the array once and verify the candidate.
• Space Complexity: O(1), as we only keep track of candidate and count.

Limitations

• The algorithm guarantees correctness only if a majority element exists (i.e., appears more than n/2 times).
• If no majority exists, we need to separately verify the candidate.

Conclusion

Moore’s Majority Vote Algorithm is one of the most efficient solutions to the classical majority element problem. It works with minimal memory and linear time, making it perfect for large datasets where efficiency matters. By combining clever cancellation with a final verification step, it ensures reliable results with almost no overhead.