DATA STRUCTURES • ALGORITHMS

Majority Element

An element that appears more than ⌊n/2⌋ times in an array. The Boyer-Moore Voting Algorithm finds this candidate in linear time and constant space.

Time

O(N)

Space

O(1)

Key Principle 1

Boyer-Moore Voting Algorithm

Key Principle 2

Candidate and Count tracking

Key Principle 3

Optimal for majority detection

Key Principle 4

Does not require sorting

MAJORITY_ELEMENT_LAB
ARRAY:
Current Step
Boyer-Moore Voting Algorithm: Find element with > n/2 occurrences.
Playback
Voting Stats ⠿
CANDIDATENone
COUNT0
Boyer-Moore Logic ⠿
1int res = 0, count = 0;
2for (int x : arr) {
3    if (count == 0) { res = x; count = 1; }
4    else if (x == res) count++;
5    else count--;
6}
7return res;
2
[0]
2
[1]
1
[2]
1
[3]
1
[4]
2
[5]
2
[6]

Loading Lab...