Shivam Jain

Posted on

# Majority Element I and II : Boyer-Moore Majority Vote algorithm

These are the questions touched :

https://leetcode.com/problems/majority-element/

https://leetcode.com/problems/majority-element-ii/description/

## History and Intent

• Introduced by Robert S. Boyer and J Strother Moore in their paper titled "MJRTY - A Fast Majority Vote Algorithm."
• Solves the problem of finding a majority element in an array (> n/2 times).
• Shows the innovation and ingenuity in tackling computational problems.

## Background and Motivation

• Boyer and Moore were known for their work in computer science and formal methods.
• Developed the Boyer-Moore theorem prover, bridging computer science and mathematics.

## Majority Element Problem

• Problem: Find an element that appears > n/2 times in an array.
• Applications in voting systems, data analysis, and distributed algorithms.
• Existing algorithms had higher complexities than desired.

## Algorithm Innovation

• Developed the Boyer-Moore Majority Vote algorithm to efficiently solve the problem.
• Based on observation and mathematical reasoning.
• Eliminates pairs of different elements, preserving the majority element.

## Publication and Impact

• Published in 1981 paper "MJRTY - A Fast Majority Vote Algorithm."
• Presented principles, correctness proofs, and applications.
• Efficient linear time complexity (O(n)) and constant space complexity (O(1)).

## Legacy and Continued Use

• Recognized for its elegance and efficiency.
• Extended to various domains beyond computer science.
• Variations used to solve related problems (> n/3 times).

## Boyer-Moore Majority Vote Algorithm Overview

• Purpose: Efficiently identifies the majority element in an array (> n/2 times).
• Origin: Introduced in 1981 by Robert S. Boyer and J Strother Moore.
• Observation: Majority element's count will surpass others during traversal.

## Algorithm Steps

1. Initialization: Start with `candidate` and `count` variables.
2. Traverse the Array:
• If `count` is 0, set `candidate` as current element and increment `count`.
• If current element matches `candidate`, increment `count`.
• If different, decrement `count`.
3. Validation: `candidate` holds potential majority element. Validate if it appears > n/2 times.

## Algorithm Efficiency

• Single traversal of the array.
• Utilizes constant space for `candidate` and `count` variables.

## Application: Majority Element I

https://leetcode.com/problems/majority-element/

Here's an example of how the Boyer-Moore Majority Vote algorithm is applied to solve the Majority Element I problem:

``````class Solution:
def majorityElement(self, nums: List[int]) -> int:
candidate = None
count = 0

for vote in nums:
if count == 0:
candidate = vote
count = 1
elif candidate == vote:
count += 1
else:
count -= 1

result = 0
for check in nums:
if check == candidate:
result += 1

majority = len(nums) // 2

if result > majority:
return candidate
``````

## Application: Majority Element II

https://leetcode.com/problems/majority-element-ii/description/

For the Majority Element II problem, the Boyer-Moore Majority Vote algorithm can be adjusted to find elements that appear more than n/3 times in an array:

``````class Solution:
def majorityElement(self, nums: List[int]) -> List[int]:
mapi = {}
for i in range(len(nums)):
if nums[i] not in mapi:
mapi[nums[i]] = 0

mapi[nums[i]] += 1

n, list1 = len(nums), []
for i, v in mapi.items():
if v > n // 3:
list1.append(i)
return list1
``````