Boyer-Moore Majority Vote (JavaScript)

// Boyer-Moore majority vote: O(n) time, O(1) space.
export function majorityElement(values) {
  if (!Array.isArray(values) || values.length === 0) return null;
  let candidate = null;
  let balance = 0;
  for (const value of values) {
    if (balance === 0) {
      candidate = value;
      balance = 1;
    } else if (value === candidate) {
      balance += 1;
    } else {
      balance -= 1;
    }
  }
  let occurrences = 0;
  for (const value of values) {
    if (value === candidate) occurrences += 1;
  }
  return occurrences > values.length / 2 ? candidate : null;
}

export function majorityElements(values, threshold = 0.5) {
  if (!(threshold > 0 && threshold <= 1)) {
    throw new RangeError("threshold must be in (0, 1]");
  }
  const slots = Math.max(1, Math.ceil(1 / threshold) - 1);
  const counters = new Map();
  for (const value of values) {
    if (counters.has(value)) {
      counters.set(value, counters.get(value) + 1);
    } else if (counters.size < slots) {
      counters.set(value, 1);
    } else {
      for (const [key, count] of counters) {
        if (count === 1) counters.delete(key);
        else counters.set(key, count - 1);
      }
    }
  }
  const totals = new Map();
  for (const value of values) {
    if (counters.has(value)) totals.set(value, (totals.get(value) ?? 0) + 1);
  }
  return [...totals]
    .filter(([, count]) => count > values.length * threshold)
    .map(([value]) => value);
}