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

Concept Flow - Majority Element Moore's Voting Algorithm

Initialize candidate and count

↓

For each element in array

↓

Is count zero?

Yes→Set candidate to current element

↓

Compare current element with candidate

↓

Increment count

↓

Decrement count

↓

After loop ends, candidate is majority element

↓

Return candidate

The algorithm scans the array once, keeping track of a candidate and a count. When count is zero, it picks a new candidate. It increments or decrements count based on matches. At the end, the candidate is the majority element.

Execution Sample

DSA Python

def majority_element(nums):
    count = 0
    candidate = None
    for num in nums:
        if count == 0:
            candidate = num
        count += (1 if num == candidate else -1)
    return candidate

This code finds the majority element in the list by updating candidate and count as it scans.

Execution Table

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

💡 All elements processed; 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	Final
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's support is balanced out. We pick the current element as new candidate to find majority.

Why do we increment count only if current element equals candidate?

Incrementing count when element matches candidate (Steps 3,7,8) strengthens candidate's support; decrementing otherwise weakens it (Step 5). This balances votes.

How does the algorithm guarantee the candidate is the majority element?

Because majority element appears more than half times, it cannot be fully canceled out by others. After full scan (Step 9), candidate holds majority.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what happens to count and candidate?

A Count resets to zero and candidate changes to 2

B Count decrements to zero but candidate stays 3

C Count increments and candidate changes to 2

D Count stays same and candidate changes to 4

💡 Hint

Check Step 5 row in execution_table: candidate before is 3, count before is 1, candidate after is 3, count after is 0

At which step does the candidate change from 3 to 4?

A Step 4

B Step 5

C Step 6

D Step 7

💡 Hint

Look at candidate after column in execution_table rows for steps 5 and 6

If the input array started with [4,4,4], how would count change after first three steps?

A Count would be 3 and candidate 4

B Count would be 1 and candidate 4

C Count would be 0 and candidate 4

D Count would be 3 and candidate 3

💡 Hint

Refer to variable_tracker and execution_table logic for increments when element equals candidate

Concept Snapshot

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

Full Transcript

The Moore's Voting Algorithm finds the majority element by scanning the array once. It keeps a candidate and a count. When count is zero, it picks the current element as candidate. It increments count if the current element matches candidate, otherwise decrements count. This balances out votes. Because the majority element appears more than half the time, it cannot be fully canceled out. At the end, the candidate is the majority element. The example array [3,3,4,2,4,4,4] shows how candidate and count change step-by-step until candidate 4 remains with count 3.