Majority Element
Last Updated: February 6, 2026
Problem Description
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Example 2:
Constraints:
- n == nums.length
- 1 <= n <= 5 * 104
- -109 <= nums[i] <= 109
Follow-up: Could you solve the problem in linear time and in O(1) space?
Solve it on LeetCode
Understanding the Problem
Before diving into solutions, let us make sure we understand what a "majority element" really means.
An element is the majority if it appears more than n/2 times. This is a strict inequality. For an array of size 5, a majority element must appear at least 3 times. For an array of size 6, it must appear at least 4 times.
This definition has a powerful implication: there can be at most one majority element. Think about it. If one element appears more than half the time, there simply are not enough positions left in the array for any other element to also appear more than half the time.
The problem guarantees that a majority element always exists. In a real interview, you might want to clarify this assumption. Without it, you would need to verify that your candidate actually appears more than n/2 times before returning it.
Another key observation: since the majority element appears more than half the time, if you pair up each occurrence of the majority element with a non-majority element, you would still have majority elements left over. This insight becomes crucial when we discuss the Boyer-Moore algorithm.
Approaches
1. Brute Force
Intuition:
The brute-force method checks each element in the array and counts how many times it appears. If any element occurs more than n/2 times (where n is the length of the array), that element is the majority element.
This approach is simple to understand but inefficient because it performs a full scan for every element.
Code:
- Time Complexity: O(n^2) because for each element, we are iterating through the list to count occurrences.
- Space Complexity: O(1) because no extra space is used aside from variables.
2. HashMap
Intuition:
We can optimize the brute force approach by using a HashMap to store the frequency of each element.
Traverse the array, and increment the counter for each element encountered. The element with a frequency greater than n/2 will be the majority element.
Code:
- Time Complexity: O(n) because we iterate over the array once.
- Space Complexity: O(n) because we might store all elements in the map in the worst case.
3. Sorting
Intuition:
If we sort the array, all identical elements naturally group together. Since the majority element appears more than n/2 times, it must occupy the entire middle region of the sorted array.
That means the element at index n/2 will always be the majority element.
Code:
- Time Complexity: O(n log n) due to sorting.
- Space Complexity: O(1) when using in-place sorting (ignoring input space).
Example Walkthrough:
Input:
After sorting:
4. Boyer-Moore Voting Algorithm
Intuition:
The Boyer-Moore Voting Algorithm efficiently finds the majority element in linear time.
It maintains:
- candidate: current guess for the majority
- count: confidence in the candidate
As you scan:
- If
count == 0, adopt the current number as the newcandidate. - If the current number equals
candidate, incrementcount; otherwise, decrement it.
If a true majority exists, this process guarantees the final candidate is that majority.
Why does it work?
Think cancellation. Pair up elements as we scan:
- Each time we see a value different from the current
candidate, we “cancel” one occurrence of the candidate with that different value by doingcount--. - Each time we see the same value as the candidate, we increase
count, effectively “uncanceling” or reinforcing the candidate.
If there truly is a majority element M (appears more than ⌊n/2⌋ times), then:
- Across the entire array, every non-
Melement can be paired with at most oneMfor cancellation. - Since
Moccurs strictly more than all others combined, you cannot cancel all of theMs. There will be a surplus ofMs left unpaired. - That surplus ensures the final surviving candidate is
M.
Code:
- Time Complexity: O(n) since it passes through the array once.
- Space Complexity: O(1) since only a few additional variables are used.