Majority Element Moore's Voting Algorithm in DSA Rust

Mental Model

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

Analogy: Imagine a room where people pair up and leave if they disagree. The one left standing is the majority.

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

Dry Run Walkthrough

Input: list: [2, 2, 1, 1, 1, 2, 2]

Goal: Find the element that appears more than half the time in the list.

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: Look at next element 2, same as candidate, increment count to 2

Candidate=2, Count=2

Why: Same element increases confidence in candidate.

Step 3: Next element 1 differs, decrement count to 1

Candidate=2, Count=1

Why: Different element cancels one count of candidate.

Step 4: Next element 1 differs, decrement count to 0

Candidate=2, Count=0

Why: Count zero means candidate lost majority so far.

Step 5: Count 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 1 same as candidate, increment count to 2

Candidate=1, Count=2

Why: Same element increases count.

Step 7: Next element 2 differs, decrement count to 1

Candidate=1, Count=1

Why: Different element decreases count.

Step 8: Next element 2 differs, decrement count to 0

Candidate=1, Count=0

Why: Count zero means candidate lost majority so far.

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

Candidate=2, Count=1

Why: Reset candidate to current element when count is zero.

Result:

Candidate=2 is the majority element because it appears more than half the time.

Annotated Code

DSA Rust

fn majority_element(nums: &[i32]) -> i32 {
    let mut candidate = nums[0];
    let mut count = 1;
    for &num in nums.iter().skip(1) {
        if count == 0 {
            candidate = num; // reset candidate when count is zero
            count = 1;
        } else if num == candidate {
            count += 1; // same element increases count
        } else {
            count -= 1; // different element decreases count
        }
    }
    candidate
}

fn main() {
    let nums = [2, 2, 1, 1, 1, 2, 2];
    let result = majority_element(&nums);
    println!("{}", result);
}

if count == 0 {

reset candidate when count reaches zero

candidate = num;

choose new candidate

count = 1;

reset count for new candidate

else if num == candidate {

increment count if same element

count += 1;

increase confidence in candidate

else {

decrement count if different element

count -= 1;

reduce confidence in candidate

Output

2

Complexity Analysis

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

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

vs Alternative: Compared to counting frequencies with a hash map (O(n) time and O(n) space), this uses constant space and is more efficient.

Edge Cases

Array with one element

Returns that element as majority

DSA Rust

let mut candidate = nums[0];

Array where majority element is at the end

Algorithm still finds correct majority

DSA Rust

if count == 0 { candidate = num; count = 1; }

Array where no element appears more than half (invalid input)

Algorithm returns a candidate but it may not be majority; verification needed outside

DSA Rust

candidate returned without verification

When to Use This Pattern

When you need to find an element that appears more than half the time without extra space, use Moore's Voting Algorithm because it efficiently cancels out pairs of different elements.

Common Mistakes

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

Mistake: Assuming candidate is majority without verification in all cases
Fix: Verify candidate count if input may not have a majority element

Summary

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

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

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

Practice

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

easy

A. To sort the array in ascending order

B. To find the element that appears more than half the times in the array

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 an array.

2. Step 2: Compare with other options

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

3. Final Answer:

   To find the element that appears more than half the times in the array -> Option B

4. Quick Check:

   Majority element = element with > n/2 occurrences [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 Rust code snippets correctly initializes the variables for Moore's Voting Algorithm?

easy

A. let count = None; let candidate = None;

B. let count = 0; let candidate = 0;

C. let mut count = None; let mut candidate = 0;

D. let mut count = 0; let mut candidate = 0;

Solution

1. Step 1: Identify correct variable types and mutability

   Moore's Voting Algorithm requires mutable count and candidate variables. Candidate starts as 0 (sentinel value), count as 0.

2. Step 2: Check each option

   let mut count = 0; let mut candidate = 0; correctly uses mutable variables with candidate as 0 and count as 0. Others either lack mutability or wrong types.

3. Final Answer:

   let mut count = 0; let mut candidate = 0; -> Option D

4. Quick Check:

   Mutable count=0 and candidate=0 initialization [OK]

Hint: Candidate starts 0, count starts 0, both mutable [OK]

Common Mistakes:

• Not using mutable variables
• Initializing candidate with None instead of 0
• Using None for count variable

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

fn majority_element(nums: &[i32]) -> i32 {
    let mut count = 0;
    let mut candidate = 0;
    for &num in nums {
        if count == 0 {
            candidate = num;
        }
        if num == candidate {
            count += 1;
        } else {
            count -= 1;
        }
    }
    candidate
}

fn main() {
    let arr = [2, 2, 1, 1, 1, 2, 2];
    println!("{}", majority_element(&arr));
}

medium

A. 2

B. 1

C. 0

D. Compilation error

Solution

1. Step 1: Trace the algorithm with given array

   Array: [2, 2, 1, 1, 1, 2, 2]. Candidate and count update as follows:
   - Start: count=0, candidate=0
   - num=2, count=0 -> candidate=2, count=1
   - num=2 == candidate -> count=2
   - num=1 != candidate -> count=1
   - num=1 != candidate -> count=0
   - num=1, count=0 -> candidate=1, count=1
   - num=2 != candidate -> count=0
   - num=2, count=0 -> candidate=2, count=1

2. Step 2: Final candidate is 2

   After loop, candidate is 2, which is the majority element.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Majority element found = 2 [OK]

Hint: Track candidate and count changes stepwise [OK]

Common Mistakes:

• Not updating candidate when count is zero
• Miscounting increments and decrements
• Assuming first element is always majority

4. Identify the bug in this Rust implementation of Moore's Voting Algorithm:

fn majority_element(nums: &[i32]) -> i32 {
    let mut count = 0;
    let mut candidate = 0;
    for &num in nums {
        if count == 0 {
            candidate = num;
        }
        if num != candidate {
            count += 1;
        } else {
            count -= 1;
        }
    }
    candidate
}

medium

A. The count increment and decrement conditions are reversed

B. Candidate should be initialized to None

C. Loop should iterate over mutable references

D. Function should return Option<i32> instead of i32

Solution

1. Step 1: Analyze count update logic

   In Moore's Voting Algorithm, count increases when current number equals candidate, and decreases otherwise. Here, conditions are reversed.

2. Step 2: Identify correct logic

   Correct logic: if num == candidate { count += 1 } else { count -= 1 }.

3. Final Answer:

   The count increment and decrement conditions are reversed -> Option A

4. Quick Check:

   Count updates reversed cause wrong majority [OK]

Hint: Count++ if equal candidate, else count-- [OK]

Common Mistakes:

• Swapping increment and decrement conditions
• Not resetting candidate when count is zero
• Ignoring mutability of variables

5. Given an array where no element appears more than half the time, what will Moore's Voting Algorithm return?
Example: [1, 2, 3, 4]
How can you modify the algorithm to correctly handle this case?

hard

A. It returns zero; change candidate initialization to -1

B. It returns None automatically; no modification needed

C. It returns a candidate anyway; add a verification step counting candidate occurrences

D. It panics at runtime; wrap code in Result to handle errors

Solution

1. Step 1: Understand algorithm behavior without majority

   Moore's Voting Algorithm always returns a candidate even if no majority exists, because it only finds a potential majority.

2. Step 2: Modify algorithm to verify candidate

   After finding candidate, count its occurrences in the array. If count > n/2, candidate is majority; else no majority exists.

3. Final Answer:

   It returns a candidate anyway; add a verification step counting candidate occurrences -> Option C

4. Quick Check:

   Verification step needed to confirm majority [OK]

Hint: Verify candidate count after algorithm completes [OK]

Common Mistakes:

• Assuming algorithm returns None if no majority
• Not verifying candidate count after selection
• Expecting runtime errors for no majority