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