Majority Element Moore's Voting Algorithm in DSA C++ - Execution Trace

Concept Flow - Majority Element Moore's Voting Algorithm

Initialize candidate and count

↓

For each element in array

↓

Is count zero?

Yes→Set candidate = current element

↓

Is current element == candidate?

↓

Increment or decrement count accordingly

↓

Repeat for all elements

↓

Return candidate as majority element

The algorithm scans the array once, updating a candidate and count to find the majority element efficiently.

Execution Sample

DSA C++

int majorityElement(vector<int>& nums) {
    int count = 0, candidate = 0;
    for (int num : nums) {
        if (count == 0) candidate = num;
        count += (num == candidate) ? 1 : -1;
    }
    return candidate;
}

This code finds the majority element in an array using Moore's Voting Algorithm.

Execution Table

Step	Operation	Current Element	Candidate	Count	Visual State
1	Initialize	N/A	None	0	[]
2	Read element	3	3	1	[3] candidate=3, count=1
3	Read element	3	3	2	[3,3] candidate=3, count=2
4	Read element	4	3	1	[3,3,4] candidate=3, count=1 (decremented)
5	Read element	2	3	0	[3,3,4,2] candidate=3, count=0 (decremented)
6	Read element	4	4	1	[3,3,4,2,4] count=0 so candidate=4, count=1
7	Read element	4	4	2	[3,3,4,2,4,4] candidate=4, count=2
8	Read element	4	4	3	[3,3,4,2,4,4,4] candidate=4, count=3
9	End	N/A	4	3	Final candidate=4

💡 All elements processed; candidate 4 is returned as majority element.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
candidate	None	3	3	3	3	4	4	4	4
count	0	1	2	1	0	1	2	3	3

Key Moments - 3 Insights

Why do we reset the candidate when count reaches zero?

When count is zero (see Step 5), it means previous candidate lost majority support so we pick the current element as new candidate (Step 6).

Why do we increment or decrement count based on equality with candidate?

If current element equals candidate (Steps 2,3,7,8), count increases showing support; else it decreases (Steps 4,5) showing opposition.

Does the algorithm guarantee the candidate is the majority element?

Yes, if a majority element exists, it will be the candidate at the end (Step 9). Otherwise, verification is needed.

Visual Quiz - 3 Questions

Look at the execution table, what is the candidate after processing the 5th element?

A 2

B 4

C 3

D None

💡 Hint

Check the 'Candidate' column at Step 5 in the execution_table.

At which step does the candidate change from 3 to 4?

A Step 4

B Step 6

C Step 5

D Step 7

💡 Hint

Look for when count is zero and candidate is updated in the execution_table.

If the array started with [4,4,4,...], how would the count change after the first three elements?

A Count would be 3 with candidate 4

B Count would be 0 with candidate 4

C Count would be 1 with candidate 4

D Count would be 3 with candidate 3

💡 Hint

Refer to variable_tracker and how count increments when elements equal candidate.

Concept Snapshot

Moore's Voting Algorithm finds majority element in O(n) time.
Initialize candidate and count=0.
Traverse array:
 - If count=0, set candidate=current element.
 - If element == candidate, increment count.
 - Else decrement count.
Return candidate at end.

Full Transcript

Moore's Voting Algorithm efficiently finds the majority element by maintaining a candidate and a count. Initially, count is zero and candidate is undefined. As we scan the array, if count is zero, we pick the current element as candidate. For each element, if it matches the candidate, we increase count; otherwise, we decrease count. When count drops to zero, it means the candidate lost majority support, so we pick a new candidate. After processing all elements, the candidate is the majority element if one exists. This algorithm runs in linear time and uses constant space.

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