🏆 Majority Element (Boyer-Moore Voting Algorithm)

The Majority Element problem is a classic question that tests your understanding of arrays and optimization techniques.
It can be solved efficiently using a clever algorithm called the Boyer-Moore Voting Algorithm.

---

📌 Problem Statement

Given an array arr[], find the element that appears more than n/2 times.

If no such element exists, return -1.

---

🔍 Examples

Example 1:
Input: [1, 1, 2, 1, 3, 5, 1]
Output: 1

Example 2:
Input: [7]
Output: 7

Example 3:
Input: [2, 13]
Output: -1

---

🧠 Intuition

If an element appears more than n/2 times:

👉 It will always dominate the array
👉 It cannot be completely canceled out

This idea leads to the Boyer-Moore algorithm.

---

🔄 Approach 1: Brute Force

1. Count frequency of each element
2. Check if any element appears more than n/2 times

Time Complexity: O(n²)

---

🔄 Approach 2: Hash Map

1. Use a dictionary to count frequencies
2. Return element with count > n/2

💻 Code:

```python id="mj1"
def majority_element(arr):
freq = {}

for num in arr:
    freq[num] = freq.get(num, 0) + 1

n = len(arr)
for num, count in freq.items():
    if count > n // 2:
        return num

return -1

⚡ Complexity:

* Time: O(n)
* Space: O(n)

---

🔄 Approach 3: Boyer-Moore Voting Algorithm (Optimal)

Step-by-Step:

1. Initialize:

   * `candidate = None`
   * `count = 0`

2. Traverse the array:

   * If `count == 0` → choose new candidate
   * If element == candidate → increment count
   * Else → decrement count

3. Verify if candidate is actually majority

---

💻 Python Code



```python id="mj2"
def majority_element(arr):
    candidate = None
    count = 0

    # Step 1: Find candidate
    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

---

🧾 Dry Run

For: arr = [1, 1, 2, 1, 3, 5, 1]

• Start → candidate = 1
• Count increases for matching elements
• Non-matching elements reduce count
• Final candidate = 1

Verify → appears more than n/2 → valid

---

⚡ Complexity

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

---

🔥 Why This Works

• Majority element cannot be canceled out
• Uses counting + elimination strategy
• Extremely efficient

---

⚠️ Edge Cases

• Single element → return that element
• No majority → return -1
• All elements same

---

🏁 Conclusion

The Boyer-Moore algorithm is:

✔ Optimal
✔ Elegant
✔ Widely asked in interviews

Comments

[EmberNoGlow]

It's easier to write it like this

from collections import Counter
def solve(arr):
    if not arr: return -1
    c = Counter(arr).most_common(1)[0]
    return c[0] if c[1] > len(arr) // 2 else -1