Find Champion II

MediumGraph

Solution

export function findChampion(n: number, edges: number[][]): number {
  let championCount = n;
  const isChampion = new Array<boolean>(n).fill(true);
  for (const [, loser] of edges) {
    if (isChampion[loser]) {
      isChampion[loser] = false;
      championCount -= 1;
    }
  }
  return championCount === 1 ? isChampion.indexOf(true) : -1;
}

Complexity

  • Time: O(n)O(n)
  • Space: O(n)O(n)