Majority Element
Last Updated: March 19, 2026
Understanding the Problem
We need to find the element that appears more than half the time in the array. The problem guarantees such an element exists, which is an important detail. It means we don't need to verify our answer, we just need to find it.
Think about what "more than n/2 times" really means. If you lined up all the elements, the majority element takes up more than half the line. That's a powerful property. It means no other element can also appear more than n/2 times. There's always exactly one majority element. This observation opens the door to some clever algorithms beyond the obvious counting approach.
Approach 1: Hash Map
Intuition
The most natural first thought: just count everything. If we know how many times each element appears, we can simply return the one whose count exceeds n/2.
A hash map is perfect for this. We iterate through the array once, incrementing the count for each element. Then we look for the element whose count is greater than n/2. We can even check as we go and return early the moment we find an element that crosses the threshold.
Algorithm
- Create a hash map to store the count of each element.
- Iterate through the array. For each element, increment its count in the map.
- If the count for the current element exceeds
n / 2, return that element immediately. - If the loop finishes without returning (won't happen given the guarantee), return -1 as a fallback.
Example Walkthrough
Code
- Time Complexity: O(n). We iterate through the array once. Each hash map operation (get and put) is O(1) on average.
- Space Complexity: O(n). In the worst case, we store up to n/2 distinct elements in the map before finding the majority element.
This approach works correctly but uses extra space.
Can we find the majority element without remembering the count of every element? What if we exploited the fact that the majority element appears more than all others combined?
Approach 2: Sorting
Intuition
Here's a neat observation: if you sort the array, the majority element must be sitting at index n/2.
Why? Because the majority element takes up more than half the array. No matter how you arrange it, after sorting, it has to "straddle" the middle position.
Think about it this way. If the majority element is the smallest value, it occupies indices 0 through at least n/2. If it's the largest, it occupies indices starting from at most n/2 down to n-1. In every case, index n/2 is covered.
So we just sort and grab the middle element. No counting needed.
Algorithm
- Sort the array.
- Return the element at index
n / 2.
Example Walkthrough
Code
- Time Complexity: O(n log n). Dominated by the sorting step. The index lookup is O(1).
- Space Complexity: O(1) to O(n). Depends on the sorting algorithm. In-place sorts like heapsort use O(1) extra space. Languages that use mergesort (like Python's Timsort) may use O(n) extra space.
Sorting takes O(n log n) time. We're rearranging the entire array just to read one element at the midpoint. We don't need the array to be fully sorted. That's a lot of unnecessary ordering. We only need to know which element sits at position n/2.
Is there a way to find the majority element in a single pass, without sorting or extra storage? What if we used the "more than half" property to cancel out non-majority elements?
Approach 3: Boyer-Moore Voting Algorithm
Intuition
This is one of those algorithms that seems almost too simple to be correct. The idea: walk through the array maintaining a "candidate" and a counter. When you see the candidate, increment the counter. When you see something else, decrement it. If the counter hits zero, pick the current element as the new candidate and reset the counter to 1.
Think of it as a battle. The majority element has more than n/2 soldiers. Every time it encounters a different element, they "cancel out" (both lose one soldier). Since the majority has more than half the army, it can't be fully cancelled out. It will always be the last one standing.
Another way to see it: imagine pairing up different elements and removing each pair. After all cancellations, the majority element is the only one with leftover copies. The Boyer-Moore algorithm simulates this process in a single pass.
Algorithm
- Initialize
candidateto any value andcountto 0. - Iterate through each element in the array:
- If
countis 0, set the current element as the newcandidateand setcountto 1. - Otherwise, if the current element equals
candidate, incrementcount. - Otherwise, decrement
count. - Return
candidate.
Example Walkthrough:
Code
The key invariant is this: at any point during the traversal, the majority element among the remaining unprocessed elements is the same as the majority element of the entire array. When the count drops to zero, the current candidate has been "cancelled out" by an equal number of different elements. Since we've removed equal counts of the candidate and non-candidates, the majority element in the remaining portion is still the overall majority.
More formally, if the majority element appears m times (m > n/2), the maximum number of times it can be "cancelled" is n - m (the count of all other elements). Since m > n - m, the majority element's net count is always positive. So it will be the candidate when the algorithm finishes.
- Time Complexity: O(n). A single pass through the array with O(1) work per element.
- Space Complexity: O(1). Just two variables:
candidateandcount. No extra data structures at all.