Why Majority Element Moore's Voting Algorithm in DSA C?

The Big Idea

Discover how a simple counting trick can find the majority in a crowd without getting lost in details!

The Scenario

Imagine you have a huge list of votes for different candidates, and you want to find out which candidate got more than half of the votes.

Doing this by checking each vote one by one and counting for every candidate manually is like counting every single grain of rice in a big sack by hand.

The Problem

Manually counting votes for each candidate means you need to remember counts for all candidates, which takes a lot of time and memory.

It is slow and easy to make mistakes, especially if the list is very long.

The Solution

Moore's Voting Algorithm cleverly finds the majority candidate by pairing off different votes and canceling them out.

This way, it only needs to scan the list twice and uses very little extra memory.

Before vs After

✗ Before

int countVotes(int votes[], int size) {
    int counts[MAX_CANDIDATES] = {0};
    for (int i = 0; i < size; i++) {
        counts[votes[i]]++;
    }
    // Find candidate with max count
}

✓ After

int findMajority(int votes[], int size) {
    int candidate = -1, count = 0;
    for (int i = 0; i < size; i++) {
        if (count == 0) candidate = votes[i];
        count += (votes[i] == candidate) ? 1 : -1;
    }
    return candidate;
}

What It Enables

This algorithm enables fast and memory-efficient detection of a majority element in large datasets.

Real Life Example

In elections or surveys, quickly finding the candidate or option that more than half the people chose without storing all votes separately.

Key Takeaways

Manual counting is slow and memory-heavy.

Moore's Voting Algorithm uses pairing to cancel out non-majority votes.

It finds the majority element in linear time with constant space.