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 one.

Array: [2, 2, 1, 1, 1, 2, 2]
Count: 0, Candidate: None

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: Next element is 2, same as candidate, increment count to 2

Candidate=2, Count=2

Why: Same element increases confidence in candidate

Step 3: Next element is 1, different from candidate, decrement count to 1

Candidate=2, Count=1

Why: Different element cancels one occurrence of candidate

Step 4: Next element is 1, different from candidate, decrement count to 0

Candidate=2, Count=0

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

Step 5: Count is zero, update candidate to 1, count to 1

Candidate=1, Count=1

Why: Pick new candidate when count drops to zero

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

Candidate=1, Count=2

Why: Same element increases confidence in candidate

Step 7: Next element is 2, different from candidate, decrement count to 1

Candidate=1, Count=1

Why: Different element cancels one occurrence of candidate

Step 8: Next element is 2, different from candidate, decrement count to 0

Candidate=1, Count=0

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

Step 9: Count is zero, update candidate to 2, count to 1

Candidate=2, Count=1

Why: Pick new candidate when count drops to zero

Result:

Candidate=2 with final count > 0, Majority element is 2

Annotated Code

DSA C++

#include <iostream>
#include <vector>
using namespace std;

int findMajorityElement(const vector<int>& nums) {
    int candidate = 0;
    int count = 0;
    for (int num : nums) {
        if (count == 0) {
            candidate = num;  // pick new candidate
            count = 1;       // reset count
        } else if (num == candidate) {
            count++;         // same element, increase count
        } else {
            count--;         // different element, decrease count
        }
    }
    // Verify candidate is majority
    count = 0;
    for (int num : nums) {
        if (num == candidate) count++;
    }
    if (count > nums.size() / 2) return candidate;
    return -1; // no majority element
}

int main() {
    vector<int> nums = {2, 2, 1, 1, 1, 2, 2};
    int majority = findMajorityElement(nums);
    if (majority != -1) {
        cout << "Majority element is " << majority << "\n";
    } else {
        cout << "No majority element found\n";
    }
    return 0;
}

if (count == 0) { candidate = num; // pick new candidate count = 1; // reset count }

Pick new candidate when count drops to zero

else if (num == candidate) { count++; // same element, increase count }

Increase count for same candidate element

else { count--; // different element, decrease count }

Decrease count for different element

for (int num : nums) { if (num == candidate) count++; }

Verify candidate by counting occurrences

if (count > nums.size() / 2) return candidate;

Return candidate if it is 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), this uses constant space and linear time

Edge Cases

Empty array

Returns -1 indicating no majority element

DSA C++

if (count > nums.size() / 2) return candidate;

Array with one element

Returns that element as majority

DSA C++

if (count == 0) { candidate = num; count = 1; }

No majority element present

Returns -1 after verification

DSA C++

if (count > nums.size() / 2) return candidate;

When to Use This Pattern

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

Common Mistakes

Mistake: Not verifying the candidate after the first pass
Fix: Add a second pass to count candidate occurrences and confirm majority

Mistake: Resetting candidate without resetting count
Fix: Always reset count to 1 when picking a new candidate

Summary

Finds the element that appears more than half the time in a list.

Use when you want to identify a majority element efficiently without extra space.

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

Practice

1. What is the main purpose of Moore's Voting Algorithm in an array of integers?

easy

A. To count the total number of unique elements

B. To find the element that appears more than half the times

C. To find the smallest element in the array

D. To sort the array in ascending order

Solution

1. Step 1: Understand the problem Moore's Voting Algorithm solves

   It is designed to find the majority element, which is the element that appears more than half the times in the array.

2. Step 2: Compare other options

   Sorting, finding smallest element, or counting unique elements are unrelated to Moore's Voting Algorithm's goal.

3. Final Answer:

   To find the element that appears more than half the times -> Option B

4. Quick Check:

   Majority element = element with > n/2 occurrences [OK]

Hint: Majority element appears more than half times in array [OK]

Common Mistakes:

• Thinking it sorts the array
• Confusing majority element with smallest element
• Assuming it counts unique elements

2. Which of the following is the correct syntax to initialize the candidate and count variables for Moore's Voting Algorithm in C++?

easy

A. int candidate = -1, count = 0;

B. int candidate, count = 1;

C. int candidate = 0, count = -1;

D. int candidate = 0; int count;

Solution

1. Step 1: Check initialization for candidate and count

   Candidate is usually initialized to an invalid value like -1 or first element, count starts at 0.

2. Step 2: Validate options

   int candidate = -1, count = 0; initializes candidate to -1 and count to 0, which is standard and safe before iteration.

3. Final Answer:

   int candidate = -1, count = 0; -> Option A

4. Quick Check:

   Candidate = -1, Count = 0 initialization [OK]

Hint: Initialize candidate to -1 and count to 0 before loop [OK]

Common Mistakes:

• Not initializing count to 0
• Setting count to negative value
• Leaving candidate uninitialized

3. What is the output of the following C++ code snippet using Moore's Voting Algorithm?

int arr[] = {2, 2, 1, 1, 1, 2, 2};
int candidate = -1, count = 0;
for (int i = 0; i < 7; i++) {
  if (count == 0) candidate = arr[i];
  if (arr[i] == candidate) count++;
  else count--;
}
std::cout << candidate << std::endl;

medium

A. 1

B. No output

C. 0

D. 2

Solution

1. Step 1: Trace the loop and update candidate and count

   Start with candidate=-1, count=0.
   i=0: count=0, candidate=2, arr[0]=2 matches candidate, count=1
   i=1: arr[1]=2 matches candidate, count=2
   i=2: arr[2]=1 not match, count=1
   i=3: arr[3]=1 not match, count=0
   i=4: count=0, candidate=1, arr[4]=1 matches candidate, count=1
   i=5: arr[5]=2 not match, count=0
   i=6: count=0, candidate=2, arr[6]=2 matches candidate, count=1

2. Step 2: Final candidate after loop

   The candidate is 2 after the loop ends.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Final candidate = 2 [OK]

Hint: Update candidate when count is zero, increment/decrement count [OK]

Common Mistakes:

• Not updating candidate when count is zero
• Confusing increment and decrement conditions
• Assuming candidate is last element always

4. Identify the error in the following Moore's Voting Algorithm implementation snippet:

int candidate = 0, count = 0;
for (int i = 0; i < n; i++) {
  if (arr[i] == candidate) count++;
  else count--;
  if (count == 0) candidate = arr[i];
}

medium

A. Candidate update should happen before count increment/decrement

B. Count should never be decremented

C. Candidate should be initialized to -1

D. Loop should run from i = 1 to n

Solution

1. Step 1: Analyze order of candidate update and count changes

   The candidate must be updated when count is zero before comparing arr[i] with candidate to decide increment or decrement.

2. Step 2: Identify the error in code order

   Here, count is changed before candidate update, which causes wrong counting because candidate may be outdated.

3. Final Answer:

   Candidate update should happen before count increment/decrement -> Option A

4. Quick Check:

   Update candidate first when count=0 [OK]

Hint: Update candidate before count changes when count is zero [OK]

Common Mistakes:

• Updating candidate after changing count
• Initializing candidate incorrectly
• Wrong loop range

5. Given an array arr = {3, 3, 4, 2, 4, 4, 2, 4, 4}, apply Moore's Voting Algorithm to find the majority element. What is the correct majority element and why?

hard

A. 2, because it appears twice

B. 3, because it appears first in the array

C. 4, because it appears 5 times which is more than half of 9

D. No majority element exists

Solution

1. Step 1: Apply Moore's Voting Algorithm to find candidate

   Start candidate=-1, count=0.
   i=0: count=0, candidate=3, arr[0]=3 matches candidate, count=1
   i=1: arr[1]=3 matches candidate, count=2
   i=2: arr[2]=4 not match, count=1
   i=3: arr[3]=2 not match, count=0
   i=4: count=0, candidate=4, arr[4]=4 matches candidate, count=1
   i=5: arr[5]=4 matches candidate, count=2
   i=6: arr[6]=2 not match, count=1
   i=7: arr[7]=4 matches candidate, count=2
   i=8: arr[8]=4 matches candidate, count=3

2. Step 2: Verify candidate frequency

   Candidate is 4. Count occurrences of 4 in array: 5 times.
   Since 5 > 9/2 (4.5), 4 is majority element.

3. Final Answer:

   4, because it appears 5 times which is more than half of 9 -> Option C

4. Quick Check:

   Count(4) = 5 > 9/2 [OK]

Hint: Count candidate frequency after algorithm to confirm majority [OK]

Common Mistakes:

• Assuming first element is majority
• Not verifying candidate frequency
• Ignoring that majority must be > n/2