Algorithm

Majority Element

Arrays & Strings Pattern

Majority Element

Given an array nums of size n, return the majority element — the element that appears strictly more than ⌊n / 2⌋ times, i.e. on more than half of all positions. You may assume that the majority element always exists in the array.

CONSTRAINTS
  • n == nums.length
  • 1 <= n <= 5 × 10⁴
  • -10⁹ <= nums[i] <= 10⁹
  • The majority element always exists in the input
EXAMPLE 1
Input: nums = [3,2,3]
Output: 3
n = 3, so a majority needs more than ⌊3/2⌋ = 1 occurrence. 3 appears twice.
EXAMPLE 2
Input: nums = [2,2,1,1,1,2,2]
Output: 2
n = 7, so a majority needs at least 4 occurrences. 2 appears 4 times; 1 appears only 3 times.
EXAMPLE 3
Input: nums = [2,2,1,2]
Output: 2
An even length: n = 4, so ⌊n/2⌋ = 2 and a majority needs at least 3 occurrences. 2 appears 3 times.
EXAMPLE 4
Input: nums = [1]
Output: 1
One element fills 1 of 1 positions — more than ⌊1/2⌋ = 0. Trivially the majority.
To confirm the definition: I need the element appearing strictly more than ⌊n/2⌋ times — not just the most frequent one?
Correct, and the distinction matters. In [1, 1, 2, 3] the value 1 is the most frequent but fills only half the positions, so it is not a majority. You are guaranteed the strict kind exists.
Since a majority always exists, I don't need to handle a 'no majority' case?
Correct — every input has one, so no special return value is needed. (If this guarantee were ever dropped, you would have to verify that your answer really does occur more than ⌊n/2⌋ times.)
Is there any constraint on extra space?
Extra memory is acceptable for a first solution, but expect the follow-up: can you do it in O(1) space? The optimal solution can.

Finding the Majority Element is about identifying the value that appears strictly more than half the time in an array. This element is so dominant that it effectively "outvotes" every other number combined.

Majority Sorting (O(N log N))

The most intuitive solution is to sort the array. If a majority element exists, it must occupy the middle index (n // 2) because it spans more than 50% of the array's length.

python
nums.sort()
return nums[len(nums) // 2]
Hash Map Frequencies (O(N))

We can count the frequency of every number using a map. This is faster than sorting but requires extra space to store the counts.

python
counts = {}
for num in nums:
    counts[num] = counts.get(num, 0) + 1
    if counts[num] > len(nums) // 2:
        return num
3. The Insight: Numbers Advantage

The Hash Map is fast but uses extra memory. The core insight is that the majority element appears more times than all other numbers combined. This means if we let different numbers "knock each other out," the majority element is guaranteed to be the last one left standing.

Boyer-Moore Voting (O(1) space)

We maintain a "candidate" and a "strength" counter.
- If strength is 0, we adopt the current number as our candidate.
- If the current number matches the candidate, we add 1 to strength.
- If it's different, we subtract 1.
Because the majority element occurs > 50% of the time, it will survive all cancellations to remain the final candidate.

python
candidate = None
count = 0
for num in nums:
    if count == 0:
        candidate = num
    count += (1 if num == candidate else -1)
return candidate
Worked Example:[2, 2, 1, 1, 1, 2, 2]
0
2
num
1
2
2
1
3
1
4
1
5
2
6
2
The current vote count is 0, so we establish the number 2 as our majority candidate and set its count to 1.
0
2
1
2
num
2
1
3
1
4
1
5
2
6
2
We encounter another 2. Since this matches our current candidate, we increment the candidate's count to 2.
0
2
1
2
2
1
num
3
1
4
1
5
2
6
2
We encounter the number 1. Because this is different from our candidate 2, we decrement the count to 1.
0
2
1
2
2
1
3
1
num
4
1
5
2
6
2
We encounter another 1. This conflicts with our candidate 2, so we decrement the count to 0, which resets the candidate.
0
2
1
2
2
1
3
1
4
1
num
5
2
6
2
Since the count is now 0, we adopt the current number 1 as our new candidate and set its count to 1.
0
2
1
2
2
1
3
1
4
1
5
2
num
6
2
We encounter the number 2. Since it is different from our current candidate 1, we decrement the count back to 0.
0
2
1
2
2
1
3
1
4
1
5
2
6
2
num
Since the count is 0 again, we establish the number 2 as our candidate with a count of 1. Having processed the entire array, our final candidate is 2.
Interactive Strategy Visualization

Boyer-Moore Voting

Strategy: War of Attrition
2
2
1
1
1
2
2
Target Candidate
?
Current Leader
VS
Army Strength
Empty
Unit Count: 0
Pick a starting candidate.
O(N log N) Sort
→
O(N)/O(N) Hash Map
→
O(N)/O(1) Boyer-Moore