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

1. If count == 0, choose the current element as the new candidate
2. If the current element equals the candidate → increase count

3. Otherwise → decrease count
   Step 2: Verify Candidate

4. After the loop, I check if the candidate actually appears more than n //2 times

5. If yes → return it

6. 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)