Find the Majority Element

In this task, I worked on finding the majority element in an array.

A majority element is the number that appears more than ⌊n/2⌋ times in the array.

What I Did

I created a function majority_element that:

• Takes an array arr
• Returns the majority element if it exists
• Returns -1 if no majority element is found

How I Solved It

Instead of counting every element using a hashmap , I used the Boyer–Moore Voting Algorithm.

This approach finds a potential candidate in one pass and verifies it in another.

Logic Behind It

I used two variables:

• candidate → stores the potential majority element
• count → keeps track of its dominance

Step 1: Find Candidate

• If count == 0, choose the current element as the new candidate
• If the current element equals the candidate → increase count
• Otherwise → decrease count

Step 2: Verify Candidate

• After the loop, I check if the candidate actually appears more than n // 2 times
• If yes → return it
• Otherwise → return -1

Code

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

    for num in arr:
        if count == 0:
            candidate = num

        if num == candidate:
            count += 1
        else:
            count -= 1

    if arr.count(candidate) > len(arr) // 2:
        return candidate
    else:
        return -1

How It Works

• Non-majority elements eliminate each other
• The majority element, if it exists, remains as the final candidate

Time Complexity

• First pass → O(n)
• Verification → O(n)
• Total → O(n)

Space complexity → O(1)

Example Output

1
7
-1