Se você gosta de desafios de lógica e algoritmos para aquecer os motores durante a semana, provavelmente conhece a newsletter da Cassidoo, onde toda semana ela envia uma questão de entrevista técnica.

Nesse meu repositório é possível encontrar as minhas soluções dos desafios anteriores: ebdonato/cassidoo-questions

#446

Questão da Semana

Encontre o elemento majoritário em uma matriz (aquele que aparece mais de n/2 vezes) em tempo O(n) e espaço O(1) sem hashmaps.

Exemplos

> majorityElement([2, 2, 1, 1, 2, 2, 1, 2, 2])
2

> majorityElement([3, 3, 4, 2, 3, 3, 1])
3

Minha Solução

/**
 * Finds the majority element in an array using the Boyer-Moore Voting Algorithm.
 * The majority element is the element that appears more than ⌊n / 2⌋ times.
 *
 * Supports arrays with elements of multiple/mixed types (union types) and
 * accepts an optional custom equality comparator for non-primitive types.
 *
 * @param arr The array to search.
 * @param equalityFn Custom equality function, defaults to strict equality (`===`).
 * @returns The majority element.
 */
export function majorityElement<T>(
  arr: T[],
  equalityFn: (a: T, b: T) => boolean = (a: T, b: T) => a === b,
): T {
  if (arr.length === 0) {
    throw new Error("Array must not be empty");
  }

  let m: T = arr[0];
  let count = 0;

  for (const v of arr) {
    if (count) {
      count += equalityFn(v, m) ? 1 : -1;
      continue;
    }

    m = v;
    count++;
  }

  return m;
}