Majority Element Moore's Voting Algorithm in DSA C

Mental Model

Find the element that appears more than half the time by pairing and canceling different elements.

Analogy: Imagine a room where people form pairs of different opinions and leave, the opinion left at the end is the majority.

Array: [2, 2, 1, 1, 1, 2, 2]
Index:  0  1  2  3  4  5  6
Candidate: ↑ at start (index 0)
Count: 1

Dry Run Walkthrough

Input: array: [2, 2, 1, 1, 1, 2, 2]

Goal: Identify the majority element that appears more than half the time

Step 1: Start with candidate = 2 (first element), count = 1

Candidate=2, Count=1

Why: Initialize candidate and count to start tracking majority

Step 2: Look at next element 2, same as candidate, increment count to 2

Candidate=2, Count=2

Why: Same element increases confidence in candidate

Step 3: Next element 1 differs, decrement count to 1

Candidate=2, Count=1

Why: Different element cancels one occurrence of candidate

Step 4: Next element 1 differs again, decrement count to 0

Candidate=2, Count=0

Why: Count zero means candidate lost balance, need new candidate

Step 5: Count is zero, pick new candidate = 1, count = 1

Candidate=1, Count=1

Why: Reset candidate to current element when count is zero

Step 6: Next element 1 same as candidate, increment count to 2

Candidate=1, Count=2

Why: Same element increases count

Step 7: Next element 2 differs, decrement count to 1

Candidate=1, Count=1

Why: Different element cancels one count

Step 8: Next element 2 differs again, decrement count to 0

Candidate=1, Count=0

Why: Count zero means candidate lost balance again

Step 9: Count is zero, pick new candidate = 2, count = 1

Candidate=2, Count=1

Why: Reset candidate to current element when count is zero

Step 10: No more elements, verify candidate 2 appears more than half times (4 times out of 7)

Count of 2 is 4, which is > 3.5, yes majority

Why: Verification step to confirm majority element

Result:

Majority element is 2

Annotated Code

DSA C

#include <stdio.h>

// Function to find candidate for majority element
int findCandidate(int arr[], int size) {
    int count = 1;
    int candidate = arr[0];
    for (int i = 1; i < size; i++) {
        if (arr[i] == candidate) {
            count++; // same element, increase count
        } else {
            count--; // different element, decrease count
            if (count == 0) {
                candidate = arr[i]; // new candidate
                count = 1; // reset count
            }
        }
    }
    return candidate;
}

// Function to check if candidate is actually majority
int isMajority(int arr[], int size, int candidate) {
    int count = 0;
    for (int i = 0; i < size; i++) {
        if (arr[i] == candidate) {
            count++; // count occurrences
        }
    }
    return (count > size / 2);
}

int main() {
    int arr[] = {2, 2, 1, 1, 1, 2, 2};
    int size = sizeof(arr) / sizeof(arr[0]);

    int candidate = findCandidate(arr, size);

    if (isMajority(arr, size, candidate)) {
        printf("Majority element is %d\n", candidate);
    } else {
        printf("No majority element found\n");
    }
    return 0;
}

if (arr[i] == candidate) { count++; } else { count--; if (count == 0) { candidate = arr[i]; count = 1; } }

Adjust count and candidate by pairing different elements to find potential majority

for (int i = 0; i < size; i++) { if (arr[i] == candidate) { count++; } }

Count occurrences of candidate to verify majority

Output

Majority element is 2

Complexity Analysis

Time: O(n) because we scan the array twice: once to find candidate, once to verify

Space: O(1) because we use only a few variables regardless of input size

vs Alternative: Naive approach counts each element frequency with extra space O(n) or O(n^2) time; Moore's algorithm is more efficient with O(1) space and O(n) time

Edge Cases

Empty array

No candidate found, function returns first element access may cause error

DSA C

int candidate = arr[0]; // assumes non-empty array

Array with one element

That element is majority by default

DSA C

int candidate = arr[0]; // handles single element correctly

No majority element present

Candidate found but verification fails, prints no majority

DSA C

if (isMajority(arr, size, candidate)) { ... } else { ... }

When to Use This Pattern

When you need to find an element that appears more than half the time efficiently, use Moore's Voting Algorithm because it finds a candidate in one pass and verifies in another with minimal space.

Common Mistakes

Mistake: Not verifying the candidate after finding it, assuming it is always majority
Fix: Always count occurrences of candidate to confirm it appears more than half the time

Summary

Finds the element that appears more than half the time in an array efficiently.

Use when you need to identify a majority element with minimal time and space.

The key insight is pairing different elements cancels them out, leaving the majority candidate.