One value fills more than half the list. Boyer–Moore voting pairs off different values like rival fighters knocking each other off a hill, and the majority is the one left standing, in one pass and O(1) space.
▼The problem
LeetCode 169 (Easy). Given an array nums of size n, return the majority element: the value that appears more than n / 2 times. It is guaranteed to exist.
Examples (LeetCode's): [3,2,3] → 3 (scene 1); [2,2,1,1,1,2,2] → 2 (the walkthrough example: 2 appears 4 times, more than 3.5).
The solution
def majorityElement(nums):
count = 0
for x in nums:
if count == 0:
cand = x
count += 1 if x == cand else -1
return candTranscript
Majority Element. Given a list of numbers, return the one that appears more than half the time. It's guaranteed to exist: in three, two, three, it's three.
Take two, two, one, one, one, two, two. Seven numbers. Two shows up four times, more than half, so the answer is two.
The slow way counts every number against all the others: order n squared. A hash map of counts is linear time, but needs linear extra space. Sorting and taking the middle costs n log n.
The trick is Boyer-Moore voting. Keep a candidate and a count. A matching number adds one, a different number subtracts one, and when the count hits zero, the next number becomes the candidate.
Why it works: every subtraction cancels a pair of different numbers, and at most one of them is the majority. With more than half the votes, the majority can never be fully cancelled.
In code: if the count is zero, adopt the current number. Then add one on a match, or subtract one. Return the candidate.
Let's walk it. Two becomes the candidate: count one. Two again: two. A one cancels a two: one. Another one: zero. The next one is the new candidate, count one. A two cancels it: zero. The last two takes over, and two is the answer.
One pass, so order n time, and only two variables: order one space.
Pair off, cancel out, the majority stands. That's Majority Element.