Majority Element – Python (Boyer-Moore Algorithm)

🏆 Majority Element – Python (Boyer-Moore Voting Algorithm)

Hi All,

Today I solved an important problem: Finding the Majority Element in an array.

---

📌 Problem Statement

Given an array arr[], find the majority element.

👉 A majority element appears more than n/2 times.

👉 If no such element exists, return -1.

---

🔍 Examples

Example 1:

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

Output:

1

---

Example 2:

arr = [7]

Output:

7

---

Example 3:

arr = [2, 13]

Output:

-1

---

💡 Approach

🔹 Method 1: Brute Force

• Count frequency of each element
• Check if count > n/2

❌ Time: O(n²)

---

🔹 Method 2: HashMap

• Store frequency using dictionary

from collections import Counter

def majority_element(arr):
    count = Counter(arr)
    n = len(arr)

    for key in count:
        if count[key] > n // 2:
            return key
    return -1

---

🔹 Method 3: Boyer-Moore Voting Algorithm (Optimal)

👉 Most efficient approach

---

🧠 Key Idea

• Maintain a candidate
• Maintain a count
• Cancel out different elements

---

🧠 Step-by-Step Logic

1. Initialize:

   • candidate = None
   • count = 0

2. Traverse array:

   • If count == 0 → update candidate
   • If same → increment count
   • Else → decrement count

3. Verify candidate at the end

---

💻 Python Code (Optimal)

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

---

🔍 Dry Run

For:

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

Steps:

• Candidate becomes 1
• Count increases/decreases
• Final candidate = 1

Verification → appears 4 times (> 3)

---

🖥️ Sample Output

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

Input: [2, 13]
Output: -1

---

⚡ Complexity Analysis

Method	Time	Space
Brute Force	O(n²)	O(1)
HashMap	O(n)	O(n)
Boyer-Moore	O(n) ✅	O(1) ✅

---

🧠 Why this is important?

• Advanced algorithm (interview favorite)
• Works in constant space
• Efficient for large datasets

---

✅ Conclusion

This problem helped me understand:

• Frequency counting
• Optimized algorithms
• Boyer-Moore Voting Algorithm

🚀 Must-know for coding interviews!

---