Majority Element

Finding the Majority Element Using Boyer-Moore Voting Algorithm

In many array problems, a common task is to find the majority element.
A majority element is defined as an element that appears more than n/2 times in the array.

For example:

arr = [2, 2, 1, 2, 3, 2, 2]
Here, 2 appears more than half the time, so it is the majority element.

Why Not Use a Simple Approach?

1. A straightforward method would be:
2. Count the frequency of each element using a dictionary
3. Return the element with count greater than n/2

While this works, it requires extra space and takes O(n) space complexity.

Why This Approach is Used

The Boyer-Moore Voting Algorithm is used because:

1. It works in O(n) time
2. It uses O(1) space
3. It is highly efficient for large datasets

Instead of storing counts for all elements, it cleverly cancels out different elements.

Key Idea Behind the Algorithm

If an element appears more than half the time, it will always remain as the final candidate after canceling out all other elements.

Think of it like this:

Every time you see a different element, it cancels out one occurrence of the current candidate
Since the majority element appears more frequently than all others combined, it survives this cancellation process

Code Overview
class Solution:
    def majorityElement(self, arr):
        # Step 1: Find candidate using Boyer-Moore Voting Algorithm
        candidate, count = None, 0
        for num in arr:
            if count == 0:
                candidate = num
            count += (1 if num == candidate else -1)

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

Step-by-Step Explanation
Step 1: Initialize Variables

candidate, count = None, 0
candidate stores the potential majority element
count keeps track of balance between matches and mismatches

Step 2: Traverse the Array

for num in arr:

We process each element one by one.

Step 3: Reset Candidate When Count is Zero

if count == 0:
candidate = num

When the count drops to zero, we choose a new candidate.
This means previous elements have been fully canceled out.

Step 4: Update Count

count += (1 if num == candidate else -1)

1. If the current element matches the candidate, increase count
2. If it is different, decrease count

This simulates the cancellation process.

Step 5: Verify the Candidate
if arr.count(candidate) > len(arr) // 2:
return candidate

Why verification is needed:

1. The algorithm guarantees a correct candidate only if a majority element exists.
2. If no majority element exists, the candidate might be incorrect.
3. So we count its occurrences and confirm.

Example Walkthrough

Consider:

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

Process:

Start with candidate = 3
Count increases with matching elements
Decreases with different elements
Eventually, 3 remains as the candidate

Final verification confirms that 3 appears more than n/2 times.