Problem Description:

There are n teams numbered from 0 to n - 1 in a tournament.

You are given a 0-indexed 2D boolean matrix grid of size n * n. For all i, j such that 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.

If there is no team that is stronger than team a, then team a is considered the champion.

Return the team that will be the champion.

Example 1:

Input: grid = [[0,1],[0,0]] Output: 0 Explanation: There are two teams. grid[0][1] == 1 indicates that team 0 is stronger than team 1. So team 0 is the champion.

Example 2:

Input: grid = [[0,0,1],[1,0,1],[0,0,0]] Output: 1 Explanation: There are three teams. grid[1][0] == 1 indicates that team 1 is stronger than team 0. grid[1][2] == 1 indicates that team 1 is stronger than team 2. So team 1 is the champion.

Constraints:

• n == grid.length
• n == grid[i].length
• 2 <= n <= 100
• grid[i][j] is 0 or 1
• For all i, grid[i][i] == 0
• For all i != j, grid[i][j] != grid[j][i]
• The input guarantees that if team a is stronger than team b, and team b is strnoger than team c, then team a is stronger than team c.

Solution 1: Find the column with no 1s.

If all elements in column j are 0, it means no team can beat team j, so team j is the champion.

class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:
        n = len(grid)
        for col in range(n):
            has_stronger = False
            for row in range(n):
                if grid[row][col] == 1:
                    has_stronger = True
                    break
            if not has_stronger:
                return col
        return n - 1

Alternatively:

class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:
        for col_idx, col in enumerate(zip(*grid)):
            if 1 not in col:
                return col_idx

Time complexity: O(n²) Space complexity: O(1)

Solution 2: Find the row with sum equal to n-1.

class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:
        n = len(grid)
        for team, row in enumerate(grid):
            if sum(row) == n - 1:
                return team

Time complexity: O(n²) Space complexity: O(1)

Solution 3: Tournament champion approach [Time complexity: O(n)].

class Solution:
    def findChampion(self, grid: List[List[int]]) -> int:
        champion = 0
        for team, row in enumerate(grid):
            if row[champion]:
                champion = team
        return champion

Time complexity: O(n) Space complexity: O(1)