Finding the majority element seems easy…

Just count frequencies, right?

But that takes extra space.

What if you could solve it in:

O(n) time

O(1) space

That’s where Moore’s Voting Algorithm shines.

Core Idea

The algorithm works like cancelling votes.

Different elements cancel each other

Majority element survives

Phase 1: Candidate Selection

int candidate = 0, count = 0;

for (int num : nums) {

if (count == 0) {

candidate = num;

count = 1;

} else if (num == candidate) {

count++;

} else {

count--;

}

}

Think of it as:

Same element → increase count

Different element → cancel

Phase 2: Verification

count = 0;

for (int num : nums) {

if (num == candidate) count++;

}

if (count > nums.length / 2) return candidate;

return -1;

Ensures candidate is actually majority

Example

Array:

[3, 3, 4, 2, 3, 3, 3]

Majority element = 3

The Real Insight

Majority element can’t be fully cancelled

Because it appears more than half the time.

Key Insights

Uses vote cancellation logic

Requires two…