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

↓

Candidate is majority element

Start with no candidate and zero count. For each element, if count is zero, pick new candidate. Increase count if element matches candidate, else decrease. At end, candidate is majority.

Execution Sample

DSA C

int majorityElement(int* nums, int numsSize) {
    int count = 0, candidate = 0;
    for (int i = 0; i < numsSize; i++) {
        if (count == 0) candidate = nums[i];
        count += (nums[i] == candidate) ? 1 : -1;
    }
    return candidate;
}

Finds the majority element in the array using Moore's Voting Algorithm.

Execution Table

Step	Operation	Current Element	Candidate	Count	Visual State
1	Start	N/A	None	0	[]
2	Read element	2	None	0	[]
3	Count is 0, set candidate	2	2	0	[2]
4	Element == candidate, increment count	2	2	1	[2(count=1)]
5	Read element	2	2	1	[2(count=1)]
6	Element == candidate, increment count	2	2	2	[2(count=2)]
7	Read element	1	2	2	[2(count=2)]
8	Element != candidate, decrement count	1	2	1	[2(count=1)]
9	Read element	1	2	1	[2(count=1)]
10	Element != candidate, decrement count	1	2	0	[2(count=0)]
11	Read element	2	2	0	[2(count=0)]
12	Count is 0, set candidate	2	2	0	[2]
13	Element == candidate, increment count	2	2	1	[2(count=1)]
14	Read element	2	2	1	[2(count=1)]
15	Element == candidate, increment count	2	2	2	[2(count=2)]
16	End of array	N/A	2	2	[2(count=2)]

💡 Reached end of array; candidate 2 is majority element.

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	After Step 13	Final
candidate	None	2	2	2	2	2	2	2	2
count	0	0	1	2	1	0	0	1	2

Key Moments - 3 Insights

Why do we reset the candidate when count reaches zero?

When count is zero (see step 3 and 12), it means previous candidate lost majority support. We pick the current element as new candidate to try again.

Why do we increment count when element equals candidate and decrement otherwise?

Incrementing count means current candidate is supported by this element (steps 4,6,13,15). Decrementing means opposition (steps 8,10). This balances votes to find majority.

How do we know the candidate at the end is the majority element?

Moore's Voting Algorithm guarantees that if a majority element exists, it will be the candidate after full iteration (step 16).

Visual Quiz - 3 Questions

Look at the execution table, what is the candidate after step 10?

A 1

B 2

C None

D 0

💡 Hint

Check the 'Candidate' column at step 10 in the execution_table.

At which step does the count first become zero after starting?

A Step 4

B Step 12

C Step 10

D Step 8

💡 Hint

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

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

A Candidate would be 1

B Candidate would be 2

C Candidate would be None

D Candidate would be 0

💡 Hint

At step 3, candidate is set to current element when count is zero.

Concept Snapshot

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

Full Transcript

This visualization shows Moore's Voting Algorithm to find the majority element in an array. We start with no candidate and count zero. We scan each element. When count is zero, we pick the current element as candidate. If the element matches candidate, we increase count; otherwise, we decrease count. This balances votes. At the end, the candidate is the majority element. The execution table tracks each step, showing candidate and count changes. Key moments clarify why candidate resets and how count changes. The quiz tests understanding of candidate and count at specific steps. This method efficiently finds majority element in one pass.