Boyer-Moore Majority Vote Algorithm¶

The Boyer-Moore Majority Vote Algorithm is an online streaming algorithm designed to find the majority element in a sequence using linear time and constant space. It was published in 1981 by Robert S. Boyer and J Strother Moore.

1. Core Concept & Definitions¶

What is a Majority Element?¶

A majority element in an array of size \(N\) is an element that appears strictly more than \(\lfloor \frac{N}{2} \rfloor\) times.

Important: There can be at most one such element in any given array. If an element appears exactly \(N/2\) times, it is technically NOT a majority element by this definition.

The Problem of Validation¶

The algorithm works by process of elimination. It is guaranteed to find the majority element if it exists. If a majority element does not exist, the algorithm will still output one of the elements as a candidate. Therefore, the algorithm is traditionally divided into two passes:

1. Pass 1 (Find Candidate): Identify a potential majority element.
2. Pass 2 (Verify Candidate): Confirm the candidate appears \(> \frac{N}{2}\) times.

2. The Stack Analogy (Intuition)¶

Imagine you have a physical stack. This stack has a very strange rule:

It can only hold one type of item at a time.

The Rules¶

1. If the stack is empty

   • Put the current item into the stack.
   • It becomes the current Candidate.

2. If the item matches the Candidate

   • Push it onto the stack.
   • This reinforces the candidate.

3. If the item is different from the Candidate

   • Pop one item from the stack.
   • The two elements effectively cancel each other out.

Why the Majority Wins¶

Because the majority element appears more than n/2 times, it has more occurrences than all other elements combined.

• In the worst-case scenario, every non-majority element tries to cancel out one majority element.
• Even if all minority elements work together perfectly, they still do not have enough occurrences to completely eliminate the majority.
• Therefore, after all cancellations:
  • The remaining element in the stack must be the majority element (if one exists).

3. Algorithm Steps (\(N/2\) Case)¶

Pass 1: Candidate Selection¶

1. Initialize a variable candidate (can be null/empty) and a count = 0.
2. Iterate through every element x in the array:
   • If count == 0:
     • Set candidate = x.
     • Set count = 1.
   • Else if x == candidate:
     • count++
   • Else:
     • count-- (This represents a "pairing" where two different elements cancel each other out).

Pass 2: Verification¶

1. Reset count = 0.
2. Iterate through the array again.
3. Every time the element matches candidate, increment count.
4. If count > N/2, return candidate.
5. Otherwise, the array has no majority element (return -1 or null).

4. Implementation (Python)¶

def find_majority_element(nums):
    # Pass 1: Find Candidate
    candidate = None
    count = 0

    for x in nums:
        if count == 0:
            candidate = x
            count = 1
        elif x == candidate:
            count += 1
        else:
            count -= 1

    # Pass 2: Verification
    actual_count = 0
    for x in nums:
        if x == candidate:
            actual_count += 1

    if actual_count > len(nums) // 2:
        return candidate
    else:
        return -1 # Or raise Exception

5. Complexity Analysis¶

• Time Complexity: O(n)
  We perform exactly two linear scans of the input array.

• Space Complexity: O(1)
  We only maintain two variables (candidate and count), regardless of the input size.

6. Extension: Finding Elements with Frequency > n/3¶

This is the generalized version, often referred to as the Misra-Gries Heavy Hitters Algorithm.

The Logic (n/3 example)¶

If we want to find all elements that appear more than n/3 times, there can be at most two such elements because:

would be impossible.

So, we maintain:

• 2 candidates
• 2 counters

Generalized Algorithm Steps (n/k)¶

1. Maintain k - 1 candidates and k - 1 counters.

2. For each element x:

3. If x matches any existing candidate, increment its corresponding counter.

4. Else if any counter is 0, replace that candidate with x and set its counter to 1.

5. Else:

   • Decrement all k - 1 counters by 1.

6. Verification Pass

You must perform a second pass to count the actual occurrences of the remaining candidates, because the first pass only identifies the most likely heavy hitters.

7. Practice Problems¶

Comments