DSA AnimatorDSA animations
Majority ElementLC #169EasyBoyer-Moore Voting
Problem

Given an array nums of size n, return the majority element — the element that appears more than ⌊n/2⌋ times. The majority element always exists.

Example 1
Input: nums = [3,2,3]
Output: 3
Constraints: 1≤n≤5×10⁴  |  Majority element always exists  |  O(1) space?
Try Examples
Custom:
Approach
Boyer-Moore Voting Algorithm
Maintain a candidate and count. If count=0, new candidate. If current == candidate → count++. Else → count--. The majority element outlasts all opposition because it appears > n/2 times.
Array
👑 Cand: —
😴
Count: 0
Variables
Index i
—
nums[i]
—
candidate
—
count
0
Step Logic
Press ▶ Play or Next Step to begin.
🎉
Ready
0 / 0
Select an example and press Play.
Algorithm
1
Init candidate = null, count = 0
2
If count == 0: new candidate = nums[i]
3
If nums[i] == candidate: count++ (vote for)
4
If nums[i] != candidate: count-- (cancel vote)
Time
O(n)
Space
O(1)
Why It Works

Think of it as elections: each majority vote cancels one minority vote. Since the majority appears more than n/2 times, it can absorb all cancellations from minority elements and still survive with a positive count at the end.

How to solve Majority Element

LeetCode 169 · Easy · Arrays · Pattern: Boyer-Moore Voting

Why the obvious approach is slow

Counting with a hash map works, but uses O(n) space. Sorting and taking the middle costs O(n log n).

The key idea

Keep a candidate and a counter. A matching value adds 1, and a different value subtracts 1. When the counter hits 0, the next value becomes the new candidate. The majority outnumbers everything else combined, so it survives.

Remember

Pair off different values, and the majority survives. Boyer-Moore voting uses one candidate and one counter.

Run the animation above on your own input, or watch the 1:15 video explanation of Majority Element with a dry run and Java code.

More Arrays problems