Majority Element
Problem statement
You get a list of values, nums. One value appears more than half the time — that is the majority element. Return it.
You can assume a majority value always exists in the list, so you never need to handle the case where one doesn't.
This shows up anywhere a group of independent sources report a value and you need to know if more than half of them agree — for example, deciding what a majority of replicas or health checks are reporting, or which config value most nodes in a fleet are actually running.
Examples
Example 1
Input: nums = [3, 2, 3]
Output: 3
Explanation: 3 appears twice out of three values — more than half the list, so it's the majority.
Example 2
Input: nums = [2, 2, 1, 1, 1, 2, 2]
Output: 2
Explanation: 2 appears four times out of seven values. No other value appears more often, so 2 is the majority.
Hints
Approach
Optimal: Boyer-Moore voting
Intuition
Think of it as a tug-of-war. Keep one "current candidate" value and a counter for it. Every time the next value matches the candidate, the counter goes up; every time it doesn't, the counter goes down — effectively, a non-candidate value cancels out one occurrence of the candidate. If the counter ever drops to zero, everything cancelled out completely, so it's safe to forget the past and adopt whatever value comes next as the new candidate.
Why does this always land on the true majority value? Because the majority value appears more than half the time, it can never be fully cancelled out by every other value combined — no matter how the cancellations play out, at least one occurrence of the majority value survives every "reset," so it's always the one left standing (or back in the running) by the end.
This is what makes it faster and lighter than the hash map version: no map, no per-value memory, just one pass with two integers.
Steps
- Set
candidateto the first value andcountto 0. - For each value
xin the list:- If
countis 0, setcandidatetox(adopt a fresh candidate). - If
xequalscandidate, incrementcount; otherwise decrement it.
- If
- After the loop,
candidateholds the majority element — return it.
Dry run
nums = [2, 2, 1, 1, 1, 2, 2]
| step | x | count before | action | candidate | count after |
|---|---|---|---|---|---|
| 1 | 2 | 0 | count is 0 → candidate = 2; match → count++ | 2 | 1 |
| 2 | 2 | 1 | match → count++ | 2 | 2 |
| 3 | 1 | 2 | no match → count-- | 2 | 1 |
| 4 | 1 | 1 | no match → count-- | 2 | 0 |
| 5 | 1 | 0 | count is 0 → candidate = 1; match → count++ | 1 | 1 |
| 6 | 2 | 1 | no match → count-- | 1 | 0 |
| 7 | 2 | 0 | count is 0 → candidate = 2; match → count++ | 2 | 1 |
Final candidate is 2 — correct, even though the candidate flipped twice along the way.
Edge cases: a single-element list returns that element on step 1 (count goes from 0 to 1, loop ends, candidate is returned). A list where the majority value is spread out (like the trace above) still converges correctly, because the guaranteed majority can never be cancelled to zero and stay there.
Complexity
Time O(n) - Every value is visited exactly once, and each step does a constant amount of work (one comparison, one increment or decrement).
Space O(1) - Only two variables are kept: the current `candidate` and its `count`. Nothing grows with the size of the input, which is what makes Boyer-Moore the optimal approach here.
class Solution:
def majorityElement(self, nums: list[int]) -> int:
candidate = nums[0]
count = 0
for x in nums:
if count == 0:
candidate = x
count += 1 if x == candidate else -1
return candidate
if __name__ == "__main__":
print(Solution().majorityElement([3, 2, 3])) # 3
print(Solution().majorityElement([2, 2, 1, 1, 1, 2, 2])) # 2RecapThe whole problem in a few lines, for the night before
- Spot it: one value appears more than n/2 times, find it
- Idea: Boyer-Moore voting: keep a candidate and a count; same value adds one, different value removes one, zero count picks a new candidate
- Cost: O(n) time, O(1) space (a hash map is O(n) space)
- Trap: the trick only works because a majority is guaranteed to exist
Interview follow-ups
What if the input isn't guaranteed to have a majority element?
Run the same Boyer-Moore pass to get a candidate, then do a second pass to count how many times that candidate actually appears in the list. If the count is greater than
n // 2, return it as confirmed; otherwise, report that no majority element exists. This adds one more O(n) pass and no extra space, so the overall cost stays O(n) time, O(1) space.What about finding every element that appears more than n / 3 times (at most two such values can exist)?
This is the classic "Majority Element II" extension. Instead of one candidate and counter, track two candidates and two counters at once, updating them with the same increment/decrement logic (skipping a value that already matches one of the two candidates). After one pass, verify both candidates with a second counting pass, since the "more than n / 3" guarantee doesn't hold automatically the way "more than n / 2" does. Still O(n) time and O(1) space.
Frequently asked questions
Every time the count drops because of a mismatch, that's really one occurrence of the candidate being "cancelled" by one occurrence of something else. The true majority value appears more than n / 2 times — more than every other value put together — so no matter how many of its occurrences get cancelled along the way, it can never be fully wiped out. It always survives as the final candidate, even if the candidate variable flips to other values partway through, as it does in the dry run above.
The hash map is simpler to reason about and works even without the "a majority always exists" guarantee — you can use it to find the actual count of any value. But it needs O(n) extra memory in the worst case, growing with the number of distinct values. Boyer-Moore does the same job in O(1) space, which matters when the list is huge or memory is tight, and it's the answer most interviewers are looking for once you mention the follow-up about constant space.
No — the algorithm is correct for any order, because the argument only depends on counts, not positions. The dry run above deliberately uses an order where the candidate changes twice, to show that the algorithm still recovers the right answer by the end.
It's a compact stand-in for majority agreement — deciding whether more than half of a set of nodes, replicas, or health-check results agree on the same value, which is the core idea behind quorum-based systems and leader election. The O(1)-space version also naturally leads into a conversation about processing very large or streamed inputs without buffering them.
Run Boyer-Moore to get a candidate, then do one more pass counting exactly how many times that candidate appears. If the count is greater than n // 2, it's confirmed; otherwise, no majority element exists. This costs one extra O(n) pass and no extra space, and is exactly the kind of question interviewers ask as a natural follow-up.
