Majority Element
Find the value that appears more than n/2 times: count with a hash map, or use Boyer-Moore voting for O(n) time and O(1) space.
Problem Understanding
Majority Element: given an array nums of size n, return the element that appears more than ⌊n / 2⌋ times. The majority element always exists.
Example: [2, 2, 1, 1, 1, 2, 2] returns 2 (4 of 7 values).
The Intuition: Count, Then Cancel
Hash map first. The direct answer is a hash map of counts, the same counting used in Valid Anagram and Top K Frequent Elements. Return the value whose count passes n / 2. O(n) time, O(n) space.
Boyer-Moore voting. The follow-up asks for O(1) space. Picture every value voting: copies of the same value support each other, and two different values cancel each other out.
- Keep a
candidateand acount. - When
countis 0, the current value becomes the candidate. - A matching value adds a vote; any other value removes one.
The majority has more copies than all other values combined, so it cannot be cancelled away: it is the candidate at the end.
Interactive Walkthrough
nums is on top with the current value filled; below it, the candidate's votes as tokens. Try Late majority to watch the candidate change several times before the real majority takes over.
Dry Run Table
Input: nums = [2, 2, 1, 1, 1, 2, 2]
| Value | Action | Candidate | Count |
|---|---|---|---|
| 2 | count 0: pick | 2 | 1 |
| 2 | match | 2 | 2 |
| 1 | cancel | 2 | 1 |
| 1 | cancel | 2 | 0 |
| 1 | count 0: pick | 1 | 1 |
| 2 | cancel | 1 | 0 |
| 2 | count 0: pick | 2 | 1 |
Answer: 2.
The Solution Template
Boyer-Moore voting: one candidate, one count, one pass.
Majority Element Code
1var majorityElement = function(nums) {2 let candidate = 0, count = 0;3 for (const x of nums) {4 if (count === 0) candidate = x;5 count += x === candidate ? 1 : -1;6 }7 return candidate;8};
Edge Cases & Common Mistakes
- One element: it is the majority; the loop picks it immediately.
- The candidate changes: that is expected. Intermediate candidates can be wrong; only the final one is guaranteed.
- No guaranteed majority: in variants like Majority Element II or when the input may lack one, verify the candidate with a second counting pass.
- Sorting: returning
sorted(nums)[n // 2]also works, but costs O(n log n). - "At least n/2" vs "more than n/2": the guarantee needs strictly more than half; with exactly half, voting can end on the other value.
Summary
A hash map of counts finds the majority in O(n) time and O(n) space. Boyer-Moore voting does it in O(1) space: keep a candidate and a count, take a new candidate when the count hits 0, add for matches and subtract otherwise. The candidate at the end is the majority.
More practice: DSA interview questions with answers · patterns cheat sheet