These are the questions touched :
https://leetcode.com/problems/majorityelement/
https://leetcode.com/problems/majorityelementii/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 BoyerMoore 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 BoyerMoore 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).
BoyerMoore 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

Initialization: Start with
candidate
andcount
variables. 
Traverse the Array:
 If
count
is 0, setcandidate
as current element and incrementcount
.  If current element matches
candidate
, incrementcount
.  If different, decrement
count
.
 If

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
andcount
variables.
Application: Majority Element I
https://leetcode.com/problems/majorityelement/
Here's an example of how the BoyerMoore 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/majorityelementii/description/
For the Majority Element II problem, the BoyerMoore 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
Top comments (0)