Find the Majority Element

Finding the Majority Element in an Array

Problem

Given an array, find the element that appears more than n/2 times.
If no such element exists, return -1.

---

Strategy

The first thought is usually to count frequencies using a hashmap.

But that uses extra space, and the problem can be solved without it.

Instead, I used a different idea:

• Keep track of a candidate and a count
• If the same number appears, increase the count
• If a different number appears, decrease it

Over time, different elements cancel each other out.

---

Code

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

        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
        return -1

---

Key Lines Explained

• if count == 0: candidate = num
  When the count drops to zero, we reset and choose a new candidate.

• if num == candidate: count += 1
  Matching elements strengthen the candidate.

• else: count -= 1
  Different elements reduce its influence.

• arr.count(candidate) > len(arr)//2
  Final check to make sure it’s actually a majority.

---

Why This Works

If a majority element exists, it appears more than all others combined.

So even when other elements reduce the count, they can’t fully cancel it out.
That’s why the final candidate, if valid, ends up being the majority.

---

Complexity

• Time: O(n)
• Space: O(1)

---

Final Note

This problem looks like counting, but it’s really about eliminating noise.

Once you see how elements cancel each other out, the solution feels much simpler.