Majority Value
Problem
One value in a list occupies more than half of all positions. Return that value. You may assume such a value always exists, so you never have to report failure, and the list is never empty.
Examples
Input: nums = [3, 3, 4]
Output: 3
Why: 3 fills two of the three slots, which is more than halfInput: nums = [2, 2, 1, 1, 2]
Output: 2
Why: the majority value is not required to sit togetherInput: nums = [9]
Output: 9
Why: edge case, the only value trivially owns more than half the listHints
0 / 3
Counting every value in a map answers it, but the guarantee that one value owns more than half the slots is a much stronger fact than a full tally needs.
Picture every occurrence of the majority value cancelling out one occurrence of something else. Because it owns more than half, something always survives the cancelling.
Carry a current candidate and a lead counter. When the lead drops to zero, adopt the current element as the new candidate. Raise the lead when the element matches the candidate and lower it otherwise. The candidate left standing at the end is the answer.
Solution
Pairing each majority occurrence against one non-majority occurrence cancels both, and since the majority owns more than half the slots it cannot be fully cancelled. A single candidate plus a lead counter simulates that pairing without storing anything else: the lead hitting zero means the previous candidate has been fully matched, so the next element starts a fresh round. Time is O(n) with one pass, and space is O(1).
def majority_value(nums):
candidate = None
lead = 0 # how far the candidate is ahead
for x in nums:
if lead == 0: # the previous candidate was fully cancelled
candidate = x
lead += 1 if x == candidate else -1
return candidate
print(majority_value([3, 3, 4])) # -> 3
print(majority_value([2, 2, 1, 1, 2])) # -> 2
print(majority_value([9])) # -> 9Stuck on the idea rather than the code? Majority Element covers it.