Majority Element (Moore's Voting Algorithm) 🎯

Welcome to our deep dive into the world of Data Structures and Algorithms! Today, let's learn about the Majority Element, a fascinating concept in algorithms. We'll be using Moore's Voting Algorithm to find the majority element in an array, if one exists.

What is a Majority Element? 📝

A majority element in an array is an element that appears more than n/2 times, where n is the length of the array. In other words, it's an element that is "more popular" than the rest.

Why Moore's Voting Algorithm? 💡

Moore's Voting Algorithm is a simple and efficient way to find the majority element in a list. It's especially useful when dealing with large datasets, as it requires just a single pass through the array.

Let's Get Coding! ✅

We'll be writing our code in Python, but don't worry if you're not familiar with it. We'll explain everything step by step.

Here's our first code example, a simple implementation of Moore's Voting Algorithm:

python

def majorityElement(arr):
    candidate = arr[0]
    count = 1

    for num in arr:
        if num == candidate:
            count += 1
        else:
            count -= 1
            if count == 0:
                candidate = num

    return candidate

In this code, we start by assuming the first element is the majority element and increment a counter each time we encounter that element. When we encounter a different element, we decrement the counter. If the counter reaches zero, we switch the candidate to the current element. At the end, the candidate is the majority element, if one exists.

Now, let's consider a more complex scenario:

python

def majorityElement(arr):
    votes = {}

    for num in arr:
        if num not in votes:
            votes[num] = 0

        votes[num] += 1

    maxVotes = max(votes.values())
    for num, votes in votes.items():
        if votes == maxVotes:
            return num

In this version, we use a dictionary to keep track of each number and its count. At the end, we find the maximum count and return the corresponding number.

Putting It into Practice 🎯

Now, let's test our functions with some examples:

python

arr1 = [3, 2, 3, 3, 2, 4, 2, 4, 4, 4, 3]
majorityElement(arr1)  # Output: 4

arr2 = [1, 2, 1, 1, 1, 2]
majorityElement(arr2)  # Output: 1

In the first example, 4 is the majority element as it appears more than len(arr1)/2 times. In the second example, 1 is the majority element, even though it's not in the middle, but it does appear more than half the times.

Quiz Time! 💡

Question: What is the key advantage of using Moore's Voting Algorithm?

A: It requires multiple passes through the array B: It can handle ties C: It only works for sorted arrays D: It requires a linear amount of space

Correct: B Explanation: Moore's Voting Algorithm can handle ties, as it maintains a candidate and a vote count, allowing it to correctly identify multiple majority elements if they exist.