Majority Element Moore's Voting Algorithm in DSA Go - 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

↓

Return candidate as majority element

The algorithm scans the array once, updating a candidate and count to find the majority element efficiently.

Execution Sample

DSA Go

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

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

Execution Table

Step	Operation	Current Element	Candidate	Count	Visual State
1	Initialize	N/A	None	0	[]
2	Read element	3	None -> 3	0 -> 1	[3] candidate=3 count=1
3	Read element	3	3	1 -> 2	[3,3] candidate=3 count=2
4	Read element	4	3	2 -> 1	[3,3,4] candidate=3 count=1
5	Read element	2	3	1 -> 0	[3,3,4,2] candidate=3 count=0
6	Read element	4	0 -> 4	0 -> 1	[3,3,4,2,4] candidate=4 count=1
7	Read element	4	4	1 -> 2	[3,3,4,2,4,4] candidate=4 count=2
8	Read element	4	4	2 -> 3	[3,3,4,2,4,4,4] candidate=4 count=3
9	End of array	N/A	4	3	Final candidate=4 count=3

💡 Reached end of array; candidate 4 is returned as majority element

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	After Step 9
candidate	None	3	3	3	3	4	4	4	4
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 continue tracking majority.

Why do we increment count when current element equals candidate?

Incrementing count (Steps 3,7,8) strengthens confidence that candidate is majority by counting matching elements.

What happens if no majority element exists?

This algorithm assumes a majority element exists; if none exists, the candidate returned may not be a true majority.

Visual Quiz - 3 Questions

Look at the execution table, what is the candidate after Step 5?

A 3

B 4

C 2

D None

💡 Hint

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

At which step does the count first become zero?

A Step 3

B Step 5

C Step 6

D Step 9

💡 Hint

Look at the 'Count' column in the execution_table to find when it reaches zero.

If the input array started with [4,4,4], how would the candidate change at Step 2?

A Candidate would be 3

B Candidate would be 4

C Candidate would be None

D Candidate would be 0

💡 Hint

Refer to variable_tracker and see how candidate is set when count is zero at first element.

Concept Snapshot

Moore's Voting Algorithm finds majority element in O(n) time.
Initialize candidate and count=0.
Iterate array: if count=0, set candidate=current element.
If element == candidate, increment count; else decrement.
At end, candidate is majority element (if exists).

Full Transcript

Moore's Voting Algorithm scans the array once to find the majority element. It keeps track of a candidate and a count. When count is zero, it picks the current element as candidate. If the current element matches the candidate, count increases; otherwise, it decreases. This way, the candidate with the highest count at the end is the majority element. The algorithm assumes a majority element exists. The example array is processed step-by-step, showing candidate and count changes until the final candidate is returned.

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