Majority Element Moore's Voting Algorithm in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Majority Element in an array?

The Majority Element is the element that appears more than half the size of the array (n/2 times).

intermediate

What is the main idea behind Moore's Voting Algorithm?

Moore's Voting Algorithm finds the majority element by maintaining a candidate and a count. It increases the count when the same element appears and decreases it when a different element appears. The candidate at the end is the majority element if it exists.

intermediate

Why does Moore's Voting Algorithm work for finding the majority element?

Because the majority element appears more than half the time, it will remain as the candidate after canceling out all other elements with different values.

beginner

What is the time complexity of Moore's Voting Algorithm?

The time complexity is O(n) because it scans the array twice: once to find the candidate and once to verify it.

beginner

What should you do after finding the candidate in Moore's Voting Algorithm?

You should verify if the candidate actually appears more than n/2 times by counting its occurrences in the array.

What does Moore's Voting Algorithm maintain while scanning the array?

A A stack of elements

B A sorted list of elements

C A hash map of element frequencies

D A candidate element and a count

Moore's Voting Algorithm keeps track of a candidate and a count to find the majority element efficiently.

What happens to the count when the current element is different from the candidate in Moore's Voting Algorithm?

A Count increases by 1

B Count decreases by 1

C Count resets to zero

D Count stays the same

The count decreases by 1 when the current element differs from the candidate, representing cancellation.

If no element appears more than n/2 times, what will Moore's Voting Algorithm return?

A An incorrect candidate that needs verification

B The correct majority element

C Null or no candidate

D The smallest element

The algorithm returns a candidate that must be verified because it assumes a majority element exists.

What is the space complexity of Moore's Voting Algorithm?

A O(1)

B O(log n)

C O(n)

D O(n^2)

Moore's Voting Algorithm uses constant extra space, only storing a candidate and a count.

How many passes over the array does Moore's Voting Algorithm require?

A One pass

B Three passes

C Two passes

D Depends on the array size

It requires two passes: one to find the candidate and one to verify it.

Explain how Moore's Voting Algorithm finds the majority element step-by-step.

Think about how the count changes and when the candidate updates.

Why is it necessary to verify the candidate after finding it with Moore's Voting Algorithm?

Consider arrays without a majority element.

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