Majority Element
Given an array `nums` of size `n`, return the majority element (appears more than ⌊n/2⌋ times). You may assume the majority element always exists. **Core Insight:** Boyer-Moore Voting Algorithm. The majority element appears more than half the time, so if we "cancel" each non-majority element against one majority element, the majority element will still have votes left over. We maintain a `candidate` and a `count`. When count drops to 0 we pick a new candidate. **Algorithm:** Set `candidate = nums[0]`, `count = 1`. For each subsequent element: if it equals `candidate` increment count, else decrement count. If count reaches 0, set `candidate = current element` and `count = 1`. Return `candidate`. **Why it works:** The majority element has more occurrences than all others combined. Even in the worst case where every non-majority element cancels one majority element, the majority element still survives as the final candidate. **Complexity:** Time O(n) — single pass. Space O(1) — two variables.
Constraints
- •
n == nums.length - •
1 ≤ n ≤ 5 × 10⁴
def majorityElement(nums: list[int]) -> int:
candidate, count = None, 0
for num in nums:
if count == 0: candidate = num
count += 1 if num == candidate else -1
return candidate