Majority Element: Boyer-Moore Voting
Find the element appearing more than n/2 times using the linear-time, O(1)-space Boyer-Moore voting algorithm and prove its correctness.
The Majority Element Problem
Majority Element (LeetCode 169): find the element that appears more than n/2 times in an array of length n. The majority element always exists by the problem's guarantee. For [3, 2, 3], the answer is 3. For [2, 2, 1, 1, 1, 2, 2], the answer is 2 (appears 4 times out of 7). Approaches range from sorting in O(n log n) to the elegant O(n) O(1) Boyer-Moore voting algorithm.
# The majority element appears MORE than n/2 times
# So it appears more than all other elements COMBINED
examples = [
[3, 2, 3], # 3 appears 2/3 times > 1/2
[2, 2, 1, 1, 1, 2, 2], # 2 appears 4/7 times > 3.5
[1], # trivially 1
[1, 1, 2, 1], # 1 appears 3/4 times
]
for e in examples:
from collections import Counter
c = Counter(e)
print(f'Array: {e} → majority: {max(c, key=c.get)} (count {max(c.values())})')Approaches Before Boyer-Moore
Three approaches before the optimal: (1) Sorting: sort the array; the middle element is always the majority (since it appears >n/2 times). O(n log n), O(1) space. (2) Hash map: count frequencies and return the element with count > n/2. O(n) time, O(n) space. (3) Random sampling: pick a random element and verify it appears >n/2 times; expected O(1) trials (majority element is picked with probability >1/2). Boyer-Moore achieves O(n) time and O(1) space deterministically.
from collections import Counter
def majority_sort(nums):
nums.sort()
return nums[len(nums) // 2] # middle is always majority
def majority_hashmap(nums):
count = Counter(nums)
return max(count, key=count.get)
def majority_random(nums):
import random
n = len(nums)
while True:
candidate = random.choice(nums)
if nums.count(candidate) > n // 2:
return candidate
nums = [2, 2, 1, 1, 1, 2, 2]
print(majority_sort(nums[:])) # 2
print(majority_hashmap(nums)) # 2All lessons in this course
- Divide and Conquer Template
- Count Inversions Using Modified Merge Sort
- Majority Element: Boyer-Moore Voting
- Median of Two Sorted Arrays