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:
   

class Solution:
    def majorityElement(self, arr):
        # Step 1: Find candidate
        candidate = None
        count = 0

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

        # Step 2: Verify candidate
        if arr.count(candidate) > len(arr) // 2:
            return candidate
        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)