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

• 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.