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