Boyer-Moore Majority Vote & Misra-Gries Heavy Hitters

Pairwise Annihilation & The $k$-Tuple Cancellation Invariant

Suppose a stream of length $N$ contains a strict majority element $m$ with frequency $f(m) > N / 2$. Imagine pairing each occurrence of $m$ with one distinct element $x \neq m$ and deleting both from the stream. Because all non-$m$ elements combined total $N - f(m) < N / 2$, they cannot annihilate all occurrences of $m$! Robert S. Boyer and J Strother Moore (1981) turned this observation into an $O(N)$ time, $O(1)$ space streaming algorithm with two variables (candidate, count):

• If count == 0, adopt the current element $x$ as candidate = x and set count = 1.
• Else if x == candidate, increment ++count.
• Else (x != candidate), annihilate the pair by decrementing --count.

In 1982, Jayadev Misra and David Gries generalized this to find all elements occurring strictly more than $\lfloor N / k \rfloor$ times using at most $k - 1$ candidate counters: when a new element $x$ arrives and is not among the $k - 1$ tracked keys (and all $k - 1$ slots are non-zero), decrement all $k - 1$ counters by 1—forming a cancelled $k$-tuple of $k$ mutually distinct elements!

Streaming Frequency Estimation Algorithms Compared

Visualizing $k$-Tuple Cancellation ($k = 3$, Finding Elements $> N / 3$)

Two-Pass Verification Pipeline for Heavy Hitters

Production Implementation: Boyer-Moore & $k=3$ Misra-Gries with 2-Pass Verification

#include <cstdint>
#include <optional>
#include <vector>

// Boyer-Moore Majority Vote with mandatory verification pass
std::optional<int> find_majority_element(const std::vector<int>& nums) noexcept {
  int candidate = 0;
  std::size_t count = 0;

  for (int x : nums) {
    if (count == 0) {
      candidate = x;
      count = 1;
    } else if (x == candidate) {
      ++count;
    } else {
      --count;
    }
  }

  // Pass 2: Verify that candidate actually occurs > N / 2 times
  std::size_t exact = 0;
  for (int x : nums) {
    if (x == candidate) ++exact;
  }
  if (exact > nums.size() / 2) return candidate;
  return std::nullopt;
}

// Misra-Gries (k = 3): Find all elements appearing strictly more than floor(N / 3) times
std::vector<int> majority_element_n_over_3(const std::vector<int>& nums) {
  int cand1 = 0, cand2 = 1; // Initialize to distinct dummy values
  std::size_t count1 = 0, count2 = 0;

  for (int x : nums) {
    // CRITICAL: Check equality with cand1 and cand2 FIRST before checking count == 0!
    if (count1 > 0 && x == cand1) {
      ++count1;
    } else if (count2 > 0 && x == cand2) {
      ++count2;
    } else if (count1 == 0) {
      cand1 = x;
      count1 = 1;
    } else if (count2 == 0) {
      cand2 = x;
      count2 = 1;
    } else {
      // 3 distinct elements {cand1, cand2, x} annihilate each other
      --count1;
      --count2;
    }
  }

  // Pass 2: Verify exact counts of surviving candidates
  std::size_t exact1 = 0, exact2 = 0;
  for (int x : nums) {
    if (count1 > 0 && x == cand1) ++exact1;
    else if (count2 > 0 && x == cand2) ++exact2;
  }

  std::vector<int> result;
  const std::size_t threshold = nums.size() / 3;
  if (exact1 > threshold) result.push_back(cand1);
  if (exact2 > threshold) result.push_back(cand2);
  return result;
}