Finding Majority Element Using Boyer-Moore Voting Algorithm in Python

Problem Explanation

You are given an array arr[].
Your task is to find the majority element.

A majority element is an element that appears more than n/2 times in the array.

If no such element exists, return -1.

Example:

• Input: arr = [1, 1, 2, 1, 3, 5, 1]
  Output: 1

• Input: arr = [7]
  Output: 7

---

Method Used: Boyer-Moore Voting Algorithm

Idea

• Assume a candidate
• Increase count if same element appears
• Decrease count if different element appears
• Final candidate may be the majority

---

Why This Method?

• Time complexity: O(n)
• Space complexity: O(1)
• Most optimal solution
• No extra memory required

---

Python Code with Explanation

class Solution:
    def majorityElement(self, arr):

Defines the function.

---

        candidate = None
        count = 0

Initialize:

• candidate → potential majority element
• count → tracking frequency

---

        for num in arr:

Loop through the array.

---

            if count == 0:
                candidate = num

If count becomes 0, pick a new candidate.

---

            if num == candidate:
                count += 1

If current element matches candidate, increase count.

---

            else:
                count -= 1

If different, decrease count.

---

Verification Step (Important)

        if arr.count(candidate) > len(arr) // 2:
            return candidate

Check if candidate is actually majority.

---

        return -1

If not majority, return -1.

---

Complete 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

---

Step-by-Step Example

Input:

[1, 1, 2, 1, 3, 5, 1]

Process:

• Track candidate and count
• Final candidate = 1
• Verify → appears more than n/2

Output:

1

---

Key Takeaway

Boyer-Moore Voting Algorithm efficiently finds the majority element using constant space and a single pass.

---