Majority Element
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
One value appears more than half the time in the list. Find it.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1A dictionary of counts works. Can you do it with almost no extra memory?
- Hint 2Imagine two different numbers cancelling each other out. What survives at the end?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Village election: voters line up. Whenever two voters standing together support different candidates they cancel each other (both go home). Whoever has more than half of all the votes can never be wiped out, so after all the cancelling the person left standing is the winner.
- The obvious way
Count every value in a dictionary (O(n) memory), or sort and take the middle (O(n log n)).
- The key insight
Keep one candidate and a counter. Same as the candidate: counter goes up. Different: counter goes down (a pair cancels). Counter at zero: pick the current number as the new candidate. The true majority has more than half the votes, so it outlasts all the cancelling and is the final candidate.
- The algorithm
- No candidate yet, counter = 0.
- For each number: if counter is 0, this number becomes the candidate.
- If the number equals the candidate, counter + 1; otherwise counter - 1.
- The candidate left at the end is the majority (the problem guarantees one exists).
Watch it run
Examplevotes = [2, 2, 1, 1, 1, 2, 2]
First 2: no candidate, so 2 becomes the candidate.
candidate 2, counter 1
Where people slip
- This trick is valid only when a majority is guaranteed. Otherwise add a second pass to check the candidate.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def majority_element(nums):
candidate, votes = None, 0
for number in nums:
if votes == 0:
candidate = number # nobody left standing: pick a new one
votes += 1 if number == candidate else -1
return candidateNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.