Majority Element Moore's Voting Algorithm in DSA Python

Mental Model

Find the element that appears more than half the time by canceling out different elements.

Analogy: Imagine a room where people vote for their favorite color. Every time two people with different colors meet, they leave together. The color left at the end is the majority color.

Array: [2, 2, 1, 1, 1, 2, 2]
Index:  0  1  2  3  4  5  6
Candidate: ↑
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 first element as candidate=2, count=1

Candidate=2, Count=1, Array=[2, 2, 1, 1, 1, 2, 2]

Why: We need a starting point to compare others.

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

Candidate=2, Count=2, Array=[2, 2, 1, 1, 1, 2, 2]

Why: Same element increases confidence in candidate.

Step 3: Next element is 1, different from candidate, decrement count to 1

Candidate=2, Count=1, Array=[2, 2, 1, 1, 1, 2, 2]

Why: Different element cancels out one occurrence.

Step 4: Next element is 1, different from candidate, decrement count to 0

Candidate=2, Count=0, Array=[2, 2, 1, 1, 1, 2, 2]

Why: Count zero means candidate lost majority so far.

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

Candidate=1, Count=1, Array=[2, 2, 1, 1, 1, 2, 2]

Why: Reset candidate to current element.

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

Candidate=1, Count=2, Array=[2, 2, 1, 1, 1, 2, 2]

Why: Same element increases count.

Step 7: Next element is 2, different from candidate, decrement count to 1

Candidate=1, Count=1, Array=[2, 2, 1, 1, 1, 2, 2]

Why: Different element cancels out one occurrence.

Step 8: Next element is 2, different from candidate, decrement count to 0

Candidate=1, Count=0, Array=[2, 2, 1, 1, 1, 2, 2]

Why: Count zero means candidate lost majority so far.

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

Candidate=2, Count=1, Array=[2, 2, 1, 1, 1, 2, 2]

Why: Reset candidate to current element.

Result:

Candidate=2 with final count=1
Majority element is 2

Annotated Code

DSA Python

class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        candidate = None
        count = 0
        for num in nums:
            if count == 0:
                candidate = num  # reset candidate when count is zero
                count = 1
            elif num == candidate:
                count += 1  # same element increases count
            else:
                count -= 1  # different element decreases count
        return candidate

# Driver code
nums = [2, 2, 1, 1, 1, 2, 2]
sol = Solution()
print(sol.majorityElement(nums))

if count == 0: candidate = num # reset candidate when count is zero count = 1

Reset candidate to current element when count drops to zero

elif num == candidate: count += 1 # same element increases count

Increase count if current element matches candidate

else: count -= 1 # different element decreases count

Decrease count if current element 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 each element frequency using extra space O(n), Moore's algorithm uses constant space and linear time

Edge Cases

Empty list

Returns None or no candidate since no elements exist

DSA Python

candidate = None
count = 0
for num in nums:

List with one element

Returns that single element as majority

DSA Python

if count == 0:
    candidate = num
    count = 1

No majority element (less than half)

Algorithm returns a candidate but it may not be majority; verification needed if strict majority required

DSA Python

return candidate

When to Use This Pattern

When you need to find an element that appears more than half the time without extra space, use Moore's Voting Algorithm because it efficiently cancels out minority elements.

Common Mistakes

Mistake: Not resetting count to 1 when picking a new candidate
Fix: Set count = 1 immediately after assigning a new candidate

Mistake: Assuming the candidate is always majority without verification
Fix: Verify candidate frequency if problem requires strict majority confirmation

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 in linear time and constant space.

The key insight is that pairs of different elements cancel each other, leaving the majority element at the end.