CA 21 - Find the Majority Element

Problem

Given an array arr[], the task is to find the majority element.

A majority element is an element that appears strictly more than n/2 times.

If no such element exists, return -1.

Output

Example 1
Output: 1
Example 2
Output: 7
Example 3
Output: -1

My Approach

To solve this problem, I used the Boyer-Moore Voting Algorithm.

I maintain a candidate and a count.

I iterate through the array:

If count is 0, I set the current element as the candidate
If the element is equal to the candidate, I increase the count
Otherwise, I decrease the count

After this process, the candidate may be the majority element.

Then I verify the candidate by counting its occurrences.

If it appears more than n/2 times, I return it, otherwise return -1.

This works because the majority element cancels out all other elements.

This approach is efficient because:

It requires only one traversal for finding candidate
It uses constant extra space
Code

def majority_element(arr):
    candidate = None
    count = 0
    for num in arr:
        if count == 0:
            candidate = num
        if num == candidate:
            count += 1
        else:
            count -= 1
    count = 0
    for num in arr:
        if num == candidate:
            count += 1
    if count > len(arr) // 2:
        return candidate
    return -1