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

Concept Flow - Majority Element Moore's Voting Algorithm

Initialize candidate and count

↓

Iterate over each element in array

↓

If count is 0

→Set candidate to current element

↓

If current element == candidate

→Increment count

↓

Else

→Decrement count

↓

Repeat until end of array

↓

Candidate is majority element

Start with no candidate and zero count. For each element, if count is zero, pick new candidate. Increase count if element matches candidate, else decrease. At end, candidate is majority.

Execution Sample

DSA C#

int candidate = -1;
int count = 0;
foreach (int num in nums) {
  if (count == 0) candidate = num;
  count += (num == candidate) ? 1 : -1;
}
return candidate;

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

Execution Table

Step	Operation	Current Element	Candidate Before	Count Before	Candidate After	Count After	Visual State
1	Start	N/A	None	0	None	0	[]
2	Read element	2	None	0	2	1	[2] candidate=2, count=1
3	Read element	2	2	1	2	2	[2,2] candidate=2, count=2
4	Read element	1	2	2	2	1	[2,2,1] candidate=2, count=1
5	Read element	1	2	1	2	0	[2,2,1,1] candidate=2, count=0
6	Read element	1	2	0	1	1	[2,2,1,1,1] candidate=1, count=1
7	Read element	2	1	1	1	0	[2,2,1,1,1,2] candidate=1, count=0
8	Read element	2	1	0	2	1	[2,2,1,1,1,2,2] candidate=2, count=1
9	Read element	2	2	1	2	2	[2,2,1,1,1,2,2,2] candidate=2, count=2
10	End	N/A	2	2	2	2	Final candidate=2

💡 Reached end of array; candidate 2 is 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	After Step 9	Final
candidate	None	2	2	2	2	1	1	2	2	2
count	0	1	2	1	0	1	0	1	2	2

Key Moments - 3 Insights

Why do we reset the candidate when count reaches zero?

When count is zero (see Step 5 and Step 7 in execution_table), it means the previous candidate's support is balanced out by other elements. We pick the current element as a new candidate to find the majority.

Why does the count increase or decrease based on matching the candidate?

If the current element matches the candidate (e.g., Step 3), it strengthens the candidate's chance, so count increases. Otherwise (e.g., Step 4), count decreases, representing opposition.

How do we know the candidate at the end is the majority?

Moore's Voting Algorithm guarantees that if a majority element exists (more than half), it will be the candidate after one pass (see final Step 10).

Visual Quiz - 3 Questions

Look at the execution_table at Step 5. What happens to the candidate and count?

A Candidate changes to 1 and count becomes 1

B Candidate stays 2 and count becomes 0

C Candidate changes to 1 and count becomes 0

D Candidate stays 2 and count becomes 1

💡 Hint

Check columns Candidate After and Count After at Step 5 in execution_table

At which step does the candidate first change from 2 to 1?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at Candidate After column in execution_table for when candidate changes

If the array started with [1,1,1,2,2,2,2], how would the candidate after Step 3 change?

A Candidate would be 1 with count 3

B Candidate would be 2 with count 1

C Candidate would be 1 with count 1

D Candidate would be 2 with count 3

💡 Hint

Consider how count increments when elements match candidate in variable_tracker

Concept Snapshot

Moore's Voting Algorithm finds majority element in O(n) time.
Initialize candidate = None, count = 0.
For each element: if count==0, candidate = element.
If element == candidate, count++ else count--.
At end, candidate is majority if exists.
No extra space needed.

Full Transcript

Moore's Voting Algorithm finds the majority element by maintaining a candidate and a count. We start with no candidate and zero count. For each element in the array, if count is zero, we pick the current element as the new candidate. If the current element matches the candidate, we increase count; otherwise, we decrease count. This process balances out non-majority elements. At the end of one pass, the candidate holds the majority element if one exists. The 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 find the element that appears more than half the time

B. To sort the array in ascending order

C. To find the smallest element in the array

D. To count the total number of unique elements

Solution

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

   The algorithm is designed to find the majority element, which is the element that appears more than half the time in the array.

2. Step 2: Compare with other options

   Sorting, finding smallest element, or counting unique elements are not the goals of this algorithm.

3. Final Answer:

   To find the element that appears more than half the time -> Option A

4. Quick Check:

   Majority element = element with >50% frequency [OK]

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

Common Mistakes:

• Thinking it sorts the array
• Confusing majority with most frequent element without >50%
• Assuming it finds smallest or unique counts

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

easy

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

B. int candidate; int count = 1;

C. int candidate = 0; int count = 0;

D. int candidate = 0; int count = 1;

Solution

1. Step 1: Understand initialization requirements

   Candidate should start with a default value (like 0) and count should start at 0 before processing the array.

2. Step 2: Check each option

   int candidate = 0; int count = 0; initializes candidate to 0 and count to 0, which is standard. int candidate; int count = 1; leaves candidate uninitialized. int candidate = -1; int count = 0; uses -1 which may be valid but less common. int candidate = 0; int count = 1; starts count at 1 which is incorrect before any element is processed.

3. Final Answer:

   int candidate = 0; int count = 0; -> Option C

4. Quick Check:

   Initialize candidate=0 and count=0 before loop [OK]

Hint: Start count at zero before scanning array [OK]

Common Mistakes:

• Leaving candidate uninitialized
• Starting count at 1 before processing
• Using invalid default candidate values

3. What will be the output of the following C# code snippet using Moore's Voting Algorithm?

int[] nums = {2, 2, 1, 1, 1, 2, 2};
int candidate = 0, count = 0;
foreach (int num in nums) {
  if (count == 0) candidate = num;
  count += (num == candidate) ? 1 : -1;
}
Console.WriteLine(candidate);

medium

A. 1

B. 2

C. 0

D. Error

Solution

1. Step 1: Trace the candidate and count updates

   Start with candidate=0, count=0. Iterate nums:
   - num=2: count=0, candidate=2, count=1
   - num=2: same candidate, count=2
   - num=1: different, count=1
   - num=1: different, count=0
   - num=1: count=0, candidate=1, count=1
   - num=2: different, count=0
   - num=2: count=0, candidate=2, count=1

2. Step 2: Final candidate after loop

   The final candidate is 2 after processing all elements.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Final candidate = 2 [OK]

Hint: Track count changes; candidate updates when count hits zero [OK]

Common Mistakes:

• Not updating candidate when count is zero
• Confusing candidate with last element
• Ignoring count increments and decrements

4. Identify the error in the following C# implementation of Moore's Voting Algorithm:

int[] nums = {3, 3, 4, 2, 4, 4, 2, 4, 4};
int candidate = 0, count = 0;
foreach (int num in nums) {
  if (count == 0) candidate = num;
  if (num == candidate) count++;
  else count++;
}
Console.WriteLine(candidate);

medium

A. Count is incremented in both if and else, should decrement in else

B. Candidate is not updated when count is zero

C. Candidate should be initialized to -1

D. The array nums is empty

Solution

1. Step 1: Analyze count updates in loop

   Count is incremented in both if and else branches, so count never decreases. This breaks the algorithm logic.

2. Step 2: Correct the else branch

   In Moore's Voting Algorithm, count should decrement when current number is not the candidate.

3. Final Answer:

   Count is incremented in both if and else, should decrement in else -> Option A

4. Quick Check:

   Count must decrease when num != candidate [OK]

Hint: Count decreases when element differs from candidate [OK]

Common Mistakes:

• Incrementing count in else instead of decrementing
• Not updating candidate when count is zero
• Assuming candidate initialization causes error

5. Given an array int[] nums = {1, 2, 3, 2, 2, 2, 5, 2, 2}, how can you verify after Moore's Voting Algorithm that the candidate is actually the majority element?

hard

A. Sort the array and pick the middle element

B. Assume candidate is majority without verification

C. Check if candidate is the first element in the array

D. Count the occurrences of candidate in the array and check if it is more than half the array length

Solution

1. Step 1: Understand Moore's Voting Algorithm limitation

   The algorithm finds a candidate but does not guarantee it is majority if none exists.

2. Step 2: Verify candidate by counting occurrences

   Count how many times candidate appears and compare with half the array length to confirm majority.

3. Final Answer:

   Count the occurrences of candidate in the array and check if it is more than half the array length -> Option D

4. Quick Check:

   Verify candidate count > n/2 after algorithm [OK]

Hint: Always verify candidate count > half array length [OK]

Common Mistakes:

• Skipping verification step
• Assuming candidate is always majority
• Using sorting instead of counting