Majority Element Moore's Voting Algorithm in DSA Go

Mental Model

Find the element that appears more than half the time by pairing off different elements and canceling them out.

Analogy: Imagine a room where people form pairs of different opinions and leave together. The opinion left alone at the end is the majority opinion.

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 majority 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 again, decrement count to 0

Candidate=2, Count=0

Why: Count zero means candidate lost majority so far.

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

Candidate=1, Count=1

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

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

Candidate=1, Count=2

Why: Same element increases confidence in candidate.

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

Candidate=1, Count=1

Why: Different element cancels one count of candidate.

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

Candidate=1, Count=0

Why: Count zero means candidate lost majority so far.

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

Candidate=2, Count=1

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

Step 10: End of list reached

Candidate=2, Count=1

Why: The final candidate is the majority element.

Result:

Majority element is 2

Annotated Code

DSA Go

package main

import "fmt"

func majorityElement(nums []int) int {
    candidate := 0
    count := 0
    for _, num := range nums {
        if count == 0 {
            candidate = num
            count = 1
        } else if num == candidate {
            count++
        } else {
            count--
        }
    }
    return candidate
}

func main() {
    nums := []int{2, 2, 1, 1, 1, 2, 2}
    fmt.Println(majorityElement(nums))
}

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

Reset candidate and count when count drops to zero

else if num == candidate { count++ }

Increment count if current number matches candidate

else { count-- }

Decrement count if current number differs from 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 two variables regardless of input size

vs Alternative: Naive approach counts frequency of each element using extra space O(n), this uses constant space and single pass

Edge Cases

Empty list

Returns 0 as default candidate, which may be invalid

DSA Go

No explicit guard; input should be non-empty

Single element list

Returns that single element as majority

DSA Go

Handled naturally by initialization and loop

All elements same

Returns that element as majority

DSA Go

Count increments each time, no reset

When to Use This Pattern

When you need to find an element appearing more than half the time in a list, use Moore's Voting Algorithm because it finds the majority in one pass with constant space.

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 verifying
Fix: In some cases, verify candidate frequency if majority is not guaranteed

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 efficiently in one pass.

The key insight is pairing off different elements to leave the majority candidate at the end.

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 times

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

   It 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 element, or counting unique elements are not the algorithm's purpose.

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 the array length [OK]

Common Mistakes:

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

2. Which of the following Go code snippets correctly initializes the variables needed for Moore's Voting Algorithm?

easy

A. count := 0; candidate := 0

B. var count int = 1; var candidate int = -1

C. count := 0; candidate := ''

D. var count string = '0'; var candidate int = 0

Solution

1. Step 1: Identify correct variable types and initialization

   Moore's Voting Algorithm uses an integer count starting at 0 and an integer candidate initialized to 0 or any valid integer.

2. Step 2: Check each option for type correctness

   count := 0; candidate := 0 uses count and candidate as integers with proper initialization. var count int = 1; var candidate int = -1 initializes count to 1 which is not standard start. count := 0; candidate := '' uses empty string for candidate which is wrong type. var count string = '0'; var candidate int = 0 uses string type for count which is incorrect.

3. Final Answer:

   count := 0; candidate := 0 -> Option A

4. Quick Check:

   Integer count and candidate initialized to 0 [OK]

Hint: Count starts at 0, candidate is integer zero [OK]

Common Mistakes:

• Using wrong data types for count or candidate
• Starting count at 1 instead of 0
• Initializing candidate with empty string

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

arr := []int{2, 2, 1, 1, 1, 2, 2}
count := 0
candidate := 0
for _, num := range arr {
  if count == 0 {
    candidate = num
  }
  if num == candidate {
    count++
  } else {
    count--
  }
}
fmt.Println(candidate)

medium

A. 1

B. 0

C. 2

D. 3

Solution

1. Step 1: Trace the loop to find candidate

   Start with count=0, candidate=0.
   Iteration 1: count=0, candidate=2, count=1
   Iteration 2: num=2 == candidate=2, count=2
   Iteration 3: num=1 != candidate=2, count=1
   Iteration 4: num=1 != candidate=2, count=0
   Iteration 5: count=0, candidate=1, count=1
   Iteration 6: num=2 != candidate=1, count=0
   Iteration 7: count=0, candidate=2, count=1

2. Step 2: Final candidate after loop

   The candidate after the loop ends is 2.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Majority element found = 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
• Miscounting increments and decrements

4. Identify the bug in this Go code implementing Moore's Voting Algorithm:

arr := []int{3, 3, 4, 2, 4, 4, 2, 4, 4}
count := 0
candidate := 0
for i := 0; i < len(arr); i++ {
  if count == 0 {
    candidate = arr[i]
  }
  if arr[i] == candidate {
    count--
  } else {
    count++
  }
}
fmt.Println(candidate)

medium

A. Candidate is not updated when count is zero

B. Candidate initialized incorrectly

C. Loop index goes out of range

D. Count increments and decrements are reversed

Solution

1. Step 1: Analyze count update logic

   The algorithm should increase count when current element equals candidate, and decrease count otherwise.

2. Step 2: Identify the bug in code

   Here, count is decreased when arr[i] == candidate and increased otherwise, which is reversed.

3. Final Answer:

   Count increments and decrements are reversed -> Option D

4. Quick Check:

   Correct count update: increment if equal, decrement if not [OK]

Hint: Increment count if equal, decrement if different [OK]

Common Mistakes:

• Swapping increment and decrement operations
• Not updating candidate when count is zero
• Incorrect loop bounds causing runtime errors

5. Given an array where no element appears more than half the time, how can Moore's Voting Algorithm be adapted to confirm the absence of a majority element?

hard

A. Return the candidate directly without verification

B. Run the algorithm to find a candidate, then verify its count exceeds half the array length

C. Sort the array and pick the middle element

D. Count all elements and pick the one with maximum frequency without verification

Solution

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

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

2. Step 2: Adaptation to confirm majority

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

3. Final Answer:

   Run the algorithm to find a candidate, then verify its count exceeds half the array length -> Option B

4. Quick Check:

   Verify candidate count > n/2 to confirm majority [OK]

Hint: Verify candidate count after algorithm to confirm majority [OK]

Common Mistakes:

• Assuming candidate is always majority without verification
• Using sorting instead of Moore's Voting Algorithm
• Picking max frequency without checking majority condition