Find the Majority Element in Python with Boyer-Moore Vote

Use Boyer-Moore majority vote to find the element appearing more than n/2 times in an array in O(n) time and O(1) space.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 14 views 0 copies

boyer-moore majority-element array algorithm voting

Python code

15 lines

Python 3.9+

def majority_element(nums):
    candidate = None
    count = 0

    for num in nums:
        if count == 0:
            candidate = num
        count += 1 if num == candidate else -1

    return candidate

if __name__ == "__main__":
    nums = [2, 2, 1, 1, 1, 2, 2]
    result = majority_element(nums)
    print(f"Majority element: {result}")

Output

stdout

Majority element: 2

How it works

The algorithm works in two passes but code here only does the first pass because the problem guarantees a majority element exists. It maintains a candidate and a counter; whenever the counter hits zero, the current element becomes the candidate. Incrementing or decrementing the count cancels out pairs of distinct elements, leaving the majority element as the final candidate. This works because the majority element appears more than all other elements combined, so it survives cancellation.

Common mistakes

Assuming the candidate is valid without verifying it actually appears more than n/2 times — always add a second pass to confirm when no guarantee exists.
Forgetting that the algorithm only works when a majority element exists; it does not detect absence.
Using extra dictionaries or counters, which defeats the O(1) space advantage.

Variations

Add a second pass to verify the candidate's count exceeds len(nums)//2 when no majority is guaranteed.
Use collections.Counter and max() for simplicity, though it uses O(n) space.

Real-world use cases

Finding the dominant IP address in server logs to identify suspicious traffic.
Identifying the most frequent error code across millions of exception reports in a monitoring system.
Determining the majority opinion in a large-scale voting or polling dataset.

Find the Majority Element in Python with Boyer-Moore Vote

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes