Majority Element
Boyer-Moore Voting: keep a candidate and a counter. If counter is 0, pick current element as candidate. If current matches candidate, increment; otherwise decrement. The survivor is the majority element. O(1) space!
How It Works
The majority element appears more than n/2 times. A hash map solves it directly — count everything and return the element whose count exceeds n/2 — in O(n) time and O(n) space. Boyer-Moore voting eliminates the space: keep one candidate and a counter, treating matching elements as +1 and different elements as −1; when the counter hits zero, adopt the current element as the new candidate.
The majority element survives because it outnumbers all others combined, so it can absorb every cancellation and still finish as the candidate. That yields O(n) time with O(1) space. If a majority is not guaranteed to exist, a second verification pass confirms the survivor's count.
Step-by-Step Visualization
Code
static int majorityElement(int[] nums) {
int candidate = nums[0], count = 1;
for (int i = 1; i < nums.length; i++) {
if (count == 0) candidate = nums[i];
count += nums[i] == candidate ? 1 : -1;
}
return candidate;
}Tips & Gotchas
Practice Problems
- 1Majority Element
- 2Majority Element II
- 3Check If a Number Is Majority Element in a Sorted Array
About the Frequency Count Pattern
Count how often each element appears, then use those counts to answer questions like 'what's the most common?', 'are there duplicates?', or 'what appears more than n/2 times?'
If brute force is O(n²) because of a nested search, a hash map usually drops it to O(n). The tradeoff is O(n) extra space.
Common Hash Map Interview Problems
- Two Sum
- Subarray Sum Equals K
- Top K Frequent Elements
- LRU Cache
- Group Anagrams
- Longest Consecutive Sequence
Frequently Asked Questions
Why does Boyer-Moore voting actually work?
Every decrement pairs one occurrence of the candidate against one different element, and the majority element has more occurrences than all other elements combined. Even in the worst pairing, it cannot be fully cancelled out, so it must be the final surviving candidate.
Does the voting trick generalize to elements appearing more than n/3 times?
Yes — at most two elements can exceed n/3, so run the vote with two candidates and two counters, then verify both with a counting pass. This is the standard solution to Majority Element II and still uses O(1) space.
When is the plain hash map count the better answer?
Use the map when you need full frequency information anyway, when no majority is guaranteed and you want simpler logic, or in an interview warm-up before optimizing. Boyer-Moore is the follow-up answer once O(1) space is requested.