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
-
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/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
Top comments (0)