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

Concept Flow - Majority Element Moore's Voting Algorithm

Initialize candidate and count

↓

Iterate over array elements

↓

If count == 0

→Set candidate = 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. If element matches candidate, increase count; else decrease count. At end, candidate is majority.

Execution Sample

DSA Java

int candidate = -1;
int count = 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 Before	Count Before	Candidate After	Count After	Visual State
1	Start	-	None	0	None	0	[]
2	Process element	2	None	0	2	1	[2] candidate=2, count=1
3	Process element	2	2	1	2	2	[2,2] candidate=2, count=2
4	Process element	1	2	2	2	1	[2,2,1] candidate=2, count=1
5	Process element	1	2	1	2	0	[2,2,1,1] candidate=2, count=0
6	Process element	2	2	0	2	1	[2,2,1,1,2] candidate=2, count=1
7	Process element	2	2	1	2	2	[2,2,1,1,2,2] candidate=2, count=2
8	Process element	2	2	2	2	3	[2,2,1,1,2,2,2] candidate=2, count=3
9	End	-	2	3	2	3	Candidate=2 is majority element

💡 Reached end of array; candidate 2 has highest count indicating majority.

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	2	2	2	2	2	2	2	2
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 balance. We pick the current element as new candidate to try finding majority from here.

Why do we increment count if element equals candidate and decrement otherwise?

Incrementing count means current element supports candidate. Decrementing means it opposes. This balances votes to find majority (see Steps 3 and 4).

Is the candidate always the majority element after one pass?

Yes, if a majority element exists, candidate at end (Step 9) is guaranteed to be it. This works because majority count outweighs others.

Visual Quiz - 3 Questions

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

A 1

B None

C 2

D 0

💡 Hint

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

At which step does the count first become zero?

A Step 5

B Step 6

C Step 4

D Step 3

💡 Hint

Look at 'Count After' column in execution_table rows.

If the array started with element 1 instead of 2, how would the candidate after Step 2 change?

A Candidate would be 2

B Candidate would be 1

C Candidate would be None

D Candidate would be 0

💡 Hint

Candidate is set to current element when count is zero (see Step 2).

Concept Snapshot

Moore's Voting Algorithm:
- Initialize candidate = None, count = 0
- For each element:
  - If count == 0, candidate = element
  - If element == candidate, count++ else count--
- Candidate at end is majority element if exists

Full Transcript

Moore's Voting Algorithm finds the majority element in an array by maintaining a candidate and a count. Initially, candidate is None and count is zero. We iterate over each element. If count is zero, we pick the current element as the new candidate. If the current element matches the candidate, we increase count by one. Otherwise, we decrease count by one. This process balances votes for the candidate. At the end of the array, the candidate holds the majority element if one exists. This method works in one pass and uses constant extra space.

Practice

1. What is the main purpose of Moore's Voting Algorithm in arrays?

easy

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

B. To sort the array in ascending order

C. To find the smallest element in the array

D. To reverse the array 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 times in the array.

2. Step 2: Compare with other options

   Sorting, finding smallest, or reversing are unrelated to the majority element problem.

3. Final Answer:

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

4. Quick Check:

   Majority element = element appearing > n/2 times [OK]

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

Common Mistakes:

• Confusing majority element with most frequent element
• Thinking it sorts the array
• Assuming it finds smallest or largest element

2. Which of the following Java code snippets correctly initializes the count variable for Moore's Voting Algorithm?

easy

A. int count = null;

B. int count = -1;

C. int count = 0;

D. int count = 1;

Solution

1. Step 1: Check valid initialization for count

   Count starts at 1 because the first candidate is chosen and has one vote initially.

2. Step 2: Validate each option

   - -1 is invalid as count should not start negative.
   - 0 is incorrect because the first candidate is already counted once.
   - null is invalid for int type in Java.

3. Final Answer:

   int count = 1; -> Option D

4. Quick Check:

   Count starts at one for the first candidate [OK]

Hint: Count starts at one for the first candidate [OK]

Common Mistakes:

• Initializing count with 0 instead of 1
• Using null for primitive int
• Starting count negative

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

int[] arr = {2, 2, 1, 1, 1, 2, 2};
int candidate = arr[0];
int count = 1;
for (int i = 1; i < arr.length; i++) {
  if (arr[i] == candidate) count++;
  else count--;
  if (count == 0) {
    candidate = arr[i];
    count = 1;
  }
}
System.out.println(candidate);

medium

A. 2

B. 1

C. 0

D. Runtime Error

Solution

1. Step 1: Trace the candidate and count changes

   Start candidate=2, count=1
   i=1: arr[1]=2 equals candidate, count=2
   i=2: arr[2]=1 not equal, count=1
   i=3: arr[3]=1 not equal, count=0 -> reset candidate=1, count=1
   i=4: arr[4]=1 equals candidate, count=2
   i=5: arr[5]=2 not equal, count=1
   i=6: arr[6]=2 not equal, count=0 -> reset candidate=2, count=1

2. Step 2: Final candidate after loop

   Candidate is 2 after last iteration.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Final candidate = 2 [OK]

Hint: Track count changes to find final candidate [OK]

Common Mistakes:

• Not resetting candidate when count hits zero
• Confusing candidate value after last iteration
• Assuming output is the first element

4. Identify the error in this Moore's Voting Algorithm Java code snippet:

int candidate = 0;
int count = 0;
for (int num : arr) {
  if (count == 0) candidate = num;
  if (num == candidate) count++;
  else count = 0;
}
System.out.println(candidate);

medium

A. Printing candidate before loop ends

B. Candidate initialization outside loop

C. Resetting count to 0 instead of decrementing

D. Using enhanced for loop instead of index loop

Solution

1. Step 1: Analyze count update logic

   Count should decrement when current number is not candidate, but code resets count to 0.

2. Step 2: Effect of resetting count to 0

   This causes the algorithm to lose track of votes incorrectly, breaking the logic.

3. Final Answer:

   Resetting count to 0 instead of decrementing -> Option C

4. Quick Check:

   Count must decrement, not reset to zero [OK]

Hint: Decrement count when different element found [OK]

Common Mistakes:

• Resetting count to zero instead of decrementing
• Misunderstanding candidate update timing
• Confusing loop types as error

5. Given an array where no element appears more than half the time, what will Moore's Voting Algorithm return?
Example: int[] arr = {1, 2, 3, 4, 5, 6};

hard

A. The algorithm returns the element with highest frequency

B. The algorithm returns an incorrect candidate without verification

C. The algorithm throws an exception

D. The algorithm returns null

Solution

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

   The algorithm assumes a majority element exists (more than half the array).

2. Step 2: Behavior when no majority element exists

   It returns a candidate but this candidate may not actually be majority without a verification step.

3. Step 3: Verification necessity

   To confirm majority, a second pass counting candidate occurrences is needed.

4. Final Answer:

   The algorithm returns an incorrect candidate without verification -> Option B

5. Quick Check:

   No majority means candidate may be wrong [OK]

Hint: Verify candidate count if no guaranteed majority [OK]

Common Mistakes:

• Assuming algorithm throws error if no majority
• Thinking it returns null automatically
• Believing it always returns highest frequency element