Majority Element
Majority Element is LeetCode 169 (Easy). Given an integer array nums of length n, return the majority element: the value that appears more than ⌊n / 2⌋ times. The input always contains one.
The follow-up asks for O(n) time and O(1) extra space, which rules out both a hash map of counts and sorting.
- n == nums.length
- 1 <= n <= 5 * 10⁴
- -10⁹ <= nums[i] <= 10⁹
- The input is generated such that a majority element will exist in the array.
Intuition
Pair up elements that are different and throw each pair away. Every pair removes at most one copy of the majority value. The majority has more copies than every other value combined, so it can never run out: after all the throwing away, it is what is left.
The Boyer-Moore voting algorithm performs that pairing in one pass without storing any pairs. It keeps a current candidate and a count of its copies not yet cancelled. Each different value cancels one copy, each matching value adds one, and because a majority is guaranteed to exist, the survivor is the answer.
"More than half" is the signal. A value with over n/2 copies survives any cancellation of unequal pairs, so a single counter is enough. For "more than n/3" (Majority Element II) the same idea works with two candidates and two counters.
Approach
Before reading on, solve it with a hash map. Then ask: can you do it without storing counts for every value? What happens if you cancel one majority element against one other element?
Two ways to solve it
Keep one candidate and a count. A matching value adds a vote, a different one cancels a vote, and a count of 0 picks a new candidate.
- Memory: two variables, however many distinct values there are.
- Speed: one pass with no hashing.
- Caveat: if a majority is not guaranteed, verify the candidate with a second pass.
This is the optimal answer to LeetCode 169.
Count each value in a dictionary and return the first one whose count passes ⌊n/2⌋.
- Memory: one entry per distinct value, up to about n/2 entries.
- Speed: also one pass, but every step hashes.
- Flexibility: the counts also answer other frequency questions.
The obvious first answer, and fine when memory is not a concern.
Both run in one linear pass, so the difference is memory: voting keeps two variables while the map can grow with the input. That is why Boyer-Moore is the optimal majority element solution.
The steps, the code and the live demo all follow Boyer-Moore voting. The hash map code is further down, after the demo.
Start with no candidate
Set candidate = None and count = 0. The count is the number of candidate copies not yet cancelled by a different value, and starting at 0 means the very first element is adopted as the candidate.
Pick a candidate when the count is 0
Whenever count is 0, make the current element the new candidate. A count of 0 means everything seen so far has paired off evenly, so that prefix holds no majority and can be forgotten; the true majority must still win in the rest of the array.
Vote
Then compare the element with the candidate:
- same value:
count += 1, one more uncancelled copy; - different value:
count -= 1, because this element and one candidate copy cancel as a pair.
Check for 0 before voting, or the new element cancels against nothing.
Return the candidate
Return candidate after the pass. With a guaranteed majority the survivor is correct. If the input might have no majority, a second pass must count the candidate and check count > n // 2, because the vote always leaves someone standing.
Majority Element solution in Python | C++ | Java
Hash map counting
Walk the array once, adding 1 to each value's count, and return a value as soon as its count goes above half the length.
Common pitfalls
Checking count == 0 after the vote
for x in nums:
count += 1 if x == candidate else -1
if count == 0:
candidate = xfor x in nums:
if count == 0:
candidate = x
count += 1 if x == candidate else -1The new candidate must get its own vote. Switching after the vote leaves the count at 0 for the new candidate, so the next different element drives it negative and the logic breaks.
Reading the final count as the frequency
return candidate if count > len(nums) // 2 else -1
return candidate
count is the number of uncancelled votes, not how often the candidate appears. For [2, 2, 1, 1, 1, 2, 2] it ends at 1 although 2 appears 4 times. To verify a candidate, count it in a second pass.
Trusting the candidate when no majority is guaranteed
# input may have no majority return candidate
if nums.count(candidate) > len(nums) // 2:
return candidate
return -1The algorithm always ends with some candidate. For [1, 2, 3] it returns 3, which is not a majority. LeetCode 169 guarantees one exists; many interview variants do not.
Edge cases
For [6, 5, 5] the first 5 cancels the 6 and the count drops to 0, so the second 5 becomes the candidate. The first element gets no special treatment.
Complexity
nums[n // 2] is O(n log n).Four ways to find the majority element
| Method | Idea | Time | Space |
|---|---|---|---|
| Boyer-Moore voting | cancel unequal pairs; the majority survives | O(n) | O(1) |
| Hash map | count every value, return the one above n/2 | O(n) | O(n) |
| Sorting | the majority must occupy index n // 2 | O(n log n) | O(1) to O(n) |
| Majority Element II (229) | two candidates for "more than n/3" | O(n) | O(1) |
Majority Element FAQ
What is the majority element?
The value that appears more than ⌊n/2⌋ times in an array of length n. There can be at most one such value. In [2, 2, 1, 1, 1, 2, 2] it is 2 (4 of 7).
How does the Boyer-Moore voting algorithm work?
- Idea: pair each majority vote against a different value; the majority has more than half, so it survives.
- Variables:
candidateandcount, starting at none and 0. - Loop: if
count == 0, setcandidate = x; thencount += 1ifx == candidate, elsecount -= 1. - Result: return
candidate(verify with a second pass if a majority is not guaranteed). - Complexity: O(n) time, O(1) space.
- Example:
[2, 2, 1, 1, 1, 2, 2]gives 2.
Why does Boyer-Moore voting work?
Each decrement cancels one candidate vote against one different value. At most one copy of the true majority is lost per cancelled pair, and the majority has more copies than all other values together, so some copy is always left at the end, and that value must be the final candidate.
Why does sorting give the majority element?
A value filling more than half of the array must cover the middle position after sorting, whether it is the smallest or the largest value. So sorted(nums)[n // 2] is the majority.
How is Majority Element II different?
Majority Element II (229) asks for every value appearing more than ⌊n/3⌋ times. At most two such values exist, so the voting keeps two candidates and two counts, and a second pass verifies them.