Problem: Find Champion I

In a tournament with n teams, numbered from 0 to n - 1, you are given a square boolean matrix grid of size n x n. For all pairs (i, j) where 0 <= i, j <= n - 1 and i != j, if grid[i][j] == 1, then team i is stronger than team j. Otherwise, team j is stronger than team i.

The champion is defined as the team for which there exists no other team that is stronger than it.

Return the team that will be the champion.

Implementation

from typing import List

class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:
        n = len(grid)
        is_candidate = [True] * n
        
        for i in range(n):
            for j in range(n):
                if grid[i][j] == 1:
                    is_candidate[j] = False
        
        for team_id, candidate_status in enumerate(is_candidate):
            if candidate_status:
                return team_id

Problem: Find Champion II

In a tournament with n teams, numbered from 0 to n - 1, the teams are represented as nodes in a Directed Acyclic Graph (DAG). You are givan an integer n and a 2D integer aray edges of length m, where edges[i] = [u_i, v_i] denotes a directed edge from team u_i to team v_i.

A directed edge from team a to team b means team a is stronger than team b (and b is weaker then a).

The champion is defined as the team for wich there exists no other team that is stronger then it.

If there is exactly one champion, return that team's number. Otherwise, return -1.

Implementation

from typing import List

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        has_incoming_edge = [False] * n
        
        for winner, loser in edges:
            has_incoming_edge[loser] = True
        
        champion_candidate = -1
        candidate_count = 0
        
        for team_id, has_predecessor in enumerate(has_incoming_edge):
            if not has_predecessor:
                champion_candidate = team_id
                candidate_count += 1
                if candidate_count > 1:
                    return -1
        
        return champion_candidate