What is the Majority Element Problem?
Learn the majority element problem and solve it optimally in O(n) time using the Boyer-Moore voting algorithm.
Expected Interview Answer
The majority element problem asks you to find the element that appears more than n/2 times in an array of size n, and it is solved optimally in O(n) time and O(1) space using the Boyer-Moore voting algorithm, which cancels out opposing elements in pairs until only the majority survives.
A brute-force solution counts occurrences of every element in O(n squared) time, and a hash-map frequency count solves it in O(n) time but O(n) space. Sorting the array and returning the middle element also works in O(n log n) time, since a true majority element is guaranteed to occupy the middle index after sorting. The optimal approach, Boyer-Moore voting, tracks a single candidate and a count: incrementing when the current element matches the candidate, decrementing otherwise, and swapping in a new candidate whenever the count hits zero — because a true majority element always outlasts every other element canceling it out one-for-one. The algorithm assumes a majority element exists; if that guarantee is not given, a second pass is needed to verify the final candidate’s count actually exceeds n/2.
- O(n) time with O(1) space using Boyer-Moore voting
- No sorting or extra hash map required
- Single linear pass over the array
- Directly extends to the majority-element-II variant (elements appearing more than n/3 times)
AI Mentor Explanation
Imagine a stadium poll where each fan shouts the name of their favorite player, and you keep a single running favorite plus a tally: if the next shout matches your current favorite, add one to the tally, otherwise subtract one, and whenever the tally hits zero, swap in the new shout as your favorite. If one player truly has more supporters than everyone else combined, that player’s name always survives every cancellation, because every opposing shout can only cancel one supporting shout at a time. You never need a full tally sheet of every player — just the one running favorite and its count, updated shout by shout in a single pass through the crowd. This is exactly how Boyer-Moore voting finds a majority element in one linear sweep with constant extra memory.
Step-by-Step Explanation
Step 1
Understand the guarantee
A majority element appears strictly more than n/2 times; at most one such element can exist.
Step 2
Compare naive approaches
Brute-force counting is O(n squared); hash-map counting is O(n) time but O(n) space; sorting and taking the middle is O(n log n).
Step 3
Apply Boyer-Moore voting
Track one candidate and a count; matching elements increment, differing elements decrement, and count-zero swaps the candidate.
Step 4
Verify if needed
If a majority is not guaranteed to exist, re-scan to confirm the final candidate actually appears more than n/2 times.
What Interviewer Expects
- State the O(n) time, O(1) space Boyer-Moore voting solution as the optimal answer
- Explain why the vote-cancellation logic guarantees the true majority survives
- Compare tradeoffs against hash-map counting and sort-and-pick-middle approaches
- Know that a verification pass is needed if majority existence is not guaranteed
Common Mistakes
- Trusting the Boyer-Moore candidate as the answer without verifying it when a majority is not guaranteed to exist
- Confusing this with majority-element-II, which finds elements appearing more than n/3 times using two candidates
- Reaching for a hash map by default and missing the O(1)-space optimal solution
- Not explaining why cancellation logic works — treating the algorithm as a memorized trick
Best Answer (HR Friendly)
“I use the Boyer-Moore voting trick: I keep a single current candidate and a counter, adding one when I see a matching element and subtracting one otherwise, swapping in a new candidate whenever the counter hits zero. If a majority element truly exists, it always survives this cancellation process, so I find it in one pass without using any extra memory.”
Code Example
def majority_element(nums):
candidate = None
count = 0
for num in nums:
if count == 0:
candidate = num
count += 1 if num == candidate else -1
# Verification pass (needed if majority is not guaranteed to exist)
if nums.count(candidate) > len(nums) // 2:
return candidate
return NoneFollow-up Questions
- How would you solve majority-element-II, finding elements appearing more than n/3 times?
- Why is a verification pass necessary if a majority element is not guaranteed?
- Could you solve this problem using divide and conquer instead, and what would its complexity be?
- How would you find the majority element in a data stream where you cannot store the whole array?
MCQ Practice
1. What is the time and space complexity of the Boyer-Moore majority vote algorithm?
Boyer-Moore voting makes a single linear pass and tracks only one candidate and one counter, giving O(n) time and O(1) space.
2. In the Boyer-Moore voting algorithm, what happens when the count reaches zero?
A count of zero means all prior votes have canceled out, so the next element becomes the new candidate to track.
3. Why might a verification pass be needed after running Boyer-Moore voting?
If no true majority element exists, the algorithm still returns some candidate, so a follow-up count is needed to confirm it actually exceeds n/2 occurrences.
Flash Cards
What defines a majority element? — An element that appears strictly more than n/2 times in an array of size n.
What is the optimal algorithm for finding a majority element? — The Boyer-Moore voting algorithm, O(n) time and O(1) space.
Why does Boyer-Moore voting correctly find the majority element? — A true majority element cannot be fully canceled out because every opposing element only cancels one of its votes.
When is a verification pass required after Boyer-Moore voting? — When a majority element is not guaranteed to exist in the input.