Boyer-Moore Majority Vote Algorithm

Introduction

The Boyer-Moore Majority Vote algorithm is designed to find the majority element (an element that appears more than half the time) in linear time and constant space. It works by maintaining a candidate and a counter, adjusting the candidate as it iterates through the array.

In the Boyer-Moore Majority Vote algorithm, two candidates and their counters are used to handle the case where there might be more than one element that appears more than n/3 times in the array. This is particularly useful for problems where you need to find all elements that appear more than a certain fraction of the time, such as n/3.

Two Candidates

Candidate 1: Represents one potential majority element.
Candidate 2: Represents another potential majority element.
This is necessary because in an array, there can be at most two elements that appear more than n/3 times. If there were three such elements, their combined count would exceed n, which is impossible.

Counters

Count 1: Tracks the count of occurrences for Candidate 1.
Count 2: Tracks the count of occurrences for Candidate 2.
These counters help in determining whether the current candidate should be replaced or if its count should be incremented.

First Pass

Iterate through the array to find the two most frequent candidates.
Adjust the candidates and their counts based on the current element.
If the current element matches one of the candidates, increment the corresponding count.
If the current element does not match either candidate and one of the counts is zero, replace that candidate with the current element and reset the count.
If the current element does not match either candidate and both counts are non-zero, decrement both counts.

Second Pass

Verify the counts of the two candidates by iterating through the array again.
Only include candidates that appear more than n/3 times in the final result.

Consider the array [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]:

First Pass

Candidates: 3 and 4 (after processing the array)
Counts: 3 and 4 (not the actual counts, just the final state after the first pass)

Second Pass

Verify the counts of 3 and 4.
3 appears 3 times.
4 appears 4 times.
Both appear more than n/3 times (where n = 10).

        public IList<int> MajorityElement(int[] nums)
        {

            int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;

            foreach (var num in nums)
            {
                if (num == candidate1)
                {
                    count1++;
                }
                else if (num == candidate2)
                {
                    count2++;
                }
                else if (count1 == 0)
                {
                    candidate1 = num;
                    count1 = 1;
                }
                else if (count2 == 0)
                {
                    candidate2 = num;
                    count2 = 1;
                }
                else
                {
                    count1--;
                    count2--;
                }
            }

            count1 = count2 = 0;

            foreach (int num in nums)
            {
                if (candidate1 == num)
                    count1++;
                else if (candidate2 == num)
                    count2++;
            }
            var result = new List<int>();
            if (count1 > nums.Length / 3)
                result.Add(candidate1);
            if (count2 > nums.Length / 3)
                result.Add(candidate2);

            return result;
        }

Below is the Output

Output

Time Complexity: (O(n)), because it makes a constant number of passes over the array.
Space Complexity: (O(1)), because it uses a fixed amount of extra space (for the candidates and their counts), regardless of the input size.

This makes the Boyer-Moore algorithm very efficient for finding majority elements in terms of both time and space.