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

Concept Flow - Majority Element Moore's Voting Algorithm

Start with first element as candidate

↓

Iterate through array elements

↓

If count == 0, update candidate

↓

If element == candidate, increment count

↓

Else decrement count

↓

Repeat until end of array

↓

Candidate is majority element

The algorithm picks a candidate and counts its occurrences, adjusting the candidate when count drops to zero, ensuring the final candidate is the majority element.

Execution Sample

DSA Rust

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

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

Execution Table

Step	Operation	Current Element	Count Before	Candidate Before	Count After	Candidate After	Visual State
1	Start	3	0	0	1	3	[3] (candidate=3, count=1)
2	Compare element with candidate	3	1	3	2	3	[3,3] (candidate=3, count=2)
3	Compare element with candidate	4	2	3	1	3	[3,3,4] (candidate=3, count=1)
4	Compare element with candidate	2	1	3	0	3	[3,3,4,2] (candidate=3, count=0)
5	Count is zero, update candidate	2	0	3	1	2	[3,3,4,2,2] (candidate=2, count=1)
6	Compare element with candidate	2	1	2	2	2	[3,3,4,2,2,2] (candidate=2, count=2)
7	Compare element with candidate	2	2	2	3	2	[3,3,4,2,2,2,2] (candidate=2, count=3)
8	Compare element with candidate	3	3	2	2	2	[3,3,4,2,2,2,2,3] (candidate=2, count=2)
9	Compare element with candidate	3	2	2	1	2	[3,3,4,2,2,2,2,3,3] (candidate=2, count=1)
10	Compare element with candidate	3	1	2	0	2	[3,3,4,2,2,2,2,3,3,3] (candidate=2, count=0)
11	Count is zero, update candidate	3	0	2	1	3	[3,3,4,2,2,2,2,3,3,3,3] (candidate=3, count=1)
12	Compare element with candidate	3	1	3	2	3	[3,3,4,2,2,2,2,3,3,3,3,3] (candidate=3, count=2)
13	End of array	-	2	3	2	3	Final candidate is 3

💡 Reached end of array; candidate 3 is majority element

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	After 11	After 12	Final
count	0	1	2	1	0	1	2	3	2	1	0	1	2	2
candidate	0	3	3	3	3	2	2	2	2	2	2	3	3	3

Key Moments - 3 Insights

Why do we update the candidate only when count is zero?

When count reaches zero (see step 4 and 10 in execution_table), it means the previous candidate's support is balanced out by other elements, so we pick a new candidate to try to find the majority.

Why does the count increase or decrease based on element equality?

If the current element matches the candidate (steps 2, 6, 7, 8, 9, 12), count increases to show support. Otherwise, count decreases (steps 3, 4, 8, 9, 10) to represent opposition.

Is the final candidate always the majority element?

Yes, if a majority element exists, the algorithm guarantees the final candidate (step 13) is that element because it has more than half the votes.

Visual Quiz - 3 Questions

Look at the execution_table, what is the candidate after step 5?

A 3

B 2

C 4

D 0

💡 Hint

Check the 'Candidate After' column at step 5 in execution_table.

At which step does the count first become zero?

A Step 4

B Step 3

C Step 5

D Step 10

💡 Hint

Look at the 'Count After' column in execution_table to find the first zero.

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

A Candidate would be 2

B Candidate would be 3

C Candidate would be 0

D Candidate would be unchanged

💡 Hint

Candidate updates to the first element when count is zero, see step 1 in execution_table.

Concept Snapshot

Majority Element Moore's Voting Algorithm:
- Initialize count=0, candidate=0
- For each element:
  - If count==0, set candidate=element
  - If element==candidate, count++ else count--
- Final candidate is majority element
- Runs in O(n) time with O(1) space

Full Transcript

The Moore's Voting Algorithm finds the majority element by maintaining a candidate and a count. Starting with count zero, it picks the first element as candidate. For each element, if count is zero, it updates the candidate. If the element matches the candidate, it increments count; otherwise, it decrements count. This process balances out non-majority elements. At the end, the candidate is the majority element if one exists. The execution table shows each step with count and candidate changes. Key moments clarify why candidate updates happen only when count is zero and how count reflects support. The visual quiz tests understanding of candidate updates and count changes. This algorithm is efficient and uses constant space.

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