Majority Element I and II : Boyer-Moore Majority Vote algorithm
Tags: algorithms, dsa, leetcode
Published: 2023-08-10 16:15:39

These are the questions touched :

[https://leetcode.com/problems/majority-element/](url)

[https://leetcode.com/problems/majority-element-ii/description/](url)


## **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/](url)

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

```python
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/](url)

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:

```python
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
```