Majority Element Moore's Voting Algorithm in DSA Java

Mental Model

Find the element that appears more than half the time by canceling out different elements.

Analogy: Imagine a room where people vote for their favorite color. Every time two people with different colors meet, they leave the room together. The color left at the end is the majority color.

Array: [2, 2, 1, 1, 1, 2, 2]
Index:  0  1  2  3  4  5  6
Candidate: 2 ↑
Count: 1

Dry Run Walkthrough

Input: array: [2, 2, 1, 1, 1, 2, 2]

Goal: Find 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

Candidate=2, Count=2

Why: Same element increases confidence in candidate

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

Candidate=2, Count=1

Why: Different element cancels one vote from candidate

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

Candidate=2, Count=0

Why: Count zero means candidate lost all votes, pick new candidate next

Step 5: Count is zero, pick new candidate=1, count=1

Candidate=1, Count=1

Why: Reset candidate to current element when count is zero

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

Candidate=1, Count=2

Why: Same element increases confidence in candidate

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

Candidate=1, Count=1

Why: Different element cancels out the candidate's vote

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

Candidate=1, Count=0

Why: Count zero means candidate lost all votes, pick new candidate next

Step 9: Count is zero, pick new candidate=2, count=1

Candidate=2, Count=1

Why: Reset candidate to current element when count is zero

Result:

Final candidate=2 with count>0
Majority element is 2

Annotated Code

DSA Java

public class MajorityElement {
    public static int findMajorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num; // reset candidate when count is zero
                count = 1;
            } else if (num == candidate) {
                count++; // same element increases count
            } else {
                count--; // different element decreases count
            }
        }
        return candidate;
    }

    public static void main(String[] args) {
        int[] nums = {2, 2, 1, 1, 1, 2, 2};
        int majority = findMajorityElement(nums);
        System.out.println("Majority element is " + majority);
    }
}

if (count == 0) { candidate = num; // reset candidate when count is zero count = 1; }

Reset candidate and count when no current candidate

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

Increase count when element matches candidate

else { count--; // different element decreases count }

Decrease count when element differs from candidate

Output

Majority element is 2

Complexity Analysis

Time: O(n) because we scan the array once to find the candidate

Space: O(1) because we use only two variables regardless of input size

vs Alternative: Naive approach counts each element frequency with a hash map O(n) time and O(n) space; Moore's algorithm uses constant space

Edge Cases

Array with one element

Returns that element as majority

DSA Java

if (count == 0) {
    candidate = num; // reset candidate when count is zero
    count = 1;
}

Array where majority element is at the end

Algorithm still finds correct majority by canceling out others

DSA Java

else {
    count--; // different element decreases count
}

Array with all elements same

Candidate remains that element with count increasing

DSA Java

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

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 efficiently cancels out minority elements to find the majority.

Common Mistakes

Mistake: Not resetting candidate when count reaches zero
Fix: Add condition to reset candidate and count when count is zero

Mistake: Assuming candidate is always majority without verification
Fix: In some cases, verify candidate frequency if problem requires confirmation

Summary

Finds the element that appears more than half the time by canceling out different elements.

Use when you need to find the majority element efficiently in linear time and constant space.

The key insight is that pairs of different elements cancel each other, leaving the majority element at the end.

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