Majority Element
Maintained by Vikas D, software engineer
You are handed a list of numbers. One of those numbers shows up so often that its count alone is greater than half the length of the list. Your job is to report which number that is.
Because it appears strictly more than n/2 times, it is the single most common value by a wide margin, and the problem promises that such a value always exists. You never have to handle the case where no clear winner is present.
The values themselves can be large or negative, and they can be scattered anywhere in the list in any order. The only guarantee you can rely on is the frequency rule: one value crosses the half mark.
Examples
The list has length 3, so the winner must appear more than 1.5 times, meaning at least twice. The value 3 appears twice, so it is the answer.
Length is 7, so the winner needs more than 3.5 occurrences, meaning at least 4. The value 2 appears 4 times while 1 appears 3 times, so 2 wins.
Length 3 requires at least 2 copies. The value 5 appears twice, so it is the majority even though it sits at the end.
Constraints
- 1 <= n <= 5 * 10^4, where n is the length of nums
- -10^9 <= nums[i] <= 10^9
- A majority element (count greater than n/2) is guaranteed to exist
Visible test cases
- majorityElement([3,2,3]) == 3
- majorityElement([2,2,1,1,1,2,2]) == 2
- majorityElement([1]) == 1
- majorityElement([6,5,5]) == 5
- majorityElement([1,1,2,1,2,1,2,1]) == 1
Hints
Hint 1
Count how many times each value appears, then pick the one whose count passes n/2.
Hint 2
You do not need the full count of every value. You only need to track one running guess and how confident you are in it.
Hint 3
Pair off each occurrence of your current guess against any different value. Since the majority value outnumbers everything else combined, it survives all the cancellations.
Approaches
Hash map frequency count
Time O(n) · Space O(n)Tally every value, then return the first one whose tally exceeds half the array length.
- Create an empty map from value to count.
- Walk the array once, incrementing the count for each value.
- As you go, or in a second pass, check whether any count is greater than n / 2.
- Return that value once a count crosses the threshold.
Boyer-Moore voting
Time O(n) · Space O(1)Keep one candidate and a counter. Matching values raise the counter, different values lower it, and a zero counter lets a new candidate take over. The true majority outlasts every cancellation.
- Start with a counter of zero and no fixed candidate.
- For each value, if the counter is zero adopt the current value as the candidate.
- Add one to the counter when the value equals the candidate, otherwise subtract one.
- After the single pass the surviving candidate is the majority element, so return it.
Common mistakes
- Using >= n/2 instead of > n/2 as the threshold, which can misfire when a value sits exactly at half.
- With integer division, comparing count against n/2 can be off by one. Compare count * 2 > n instead to stay exact.
- In the voting method, resetting the candidate only when the counter is zero is essential. Reassigning it on every mismatch breaks the cancellation logic.
- Forgetting that values can be negative or very large, so a fixed-size array indexed by value will not work as a counter.
Follow-up variations
- Return every value that appears more than n/3 times. There can be at most two, and the voting idea extends to two candidates.
- Solve it when the array does not fit in memory and arrives as a stream you can read only once.
- What changes if the majority element is no longer guaranteed to exist? You would add a verification pass that counts the candidate.
- Find the majority element using a sort or a divide-and-conquer split, and compare the tradeoffs against the voting method.