Majority Element

When I first saw this problem, it looked very simple — just count and find the element that appears more than n/2 times. But then I realized there’s a smarter way to do it without extra space.

What I Understood is that an majority element means, It appears more than half of the array size

So if array size = n
Then element count should be > n/2

Example
[1, 1, 2, 1, 3, 5, 1]
Size = 7
n/2 = 3.5
Element 1 appears 4 times → majority

Approach

At first, I thought,
Use hashmap → count frequencies
But that takes extra space

Then I learned something interesting:
If a majority element exists, it will cancel out all other elements

Idea I Used (Boyer-Moore)
Keep a count
Keep a candidate

Logic:
If count = 0 → pick new candidate
If same element → increase count
If different → decrease count

Algorithm

    def majorityElement(self, arr):
        count = 0
        candidate = None

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

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

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