Find Champion I

Problem Description

Given a 0-indexed 2D boolean matrix grid of size n * n, determine which team out of n teams (numbered from 0 to n - 1) is the champion of a tournament. A team a is stronger than team b if grid[a][b] == 1. A team is the champion if there is no other team that is stronger than it.

Key Insights

• The matrix grid represents the strength relationships between teams.
• Each team can only have one stronger team, forming a directed graph.
• The champion is the team without any incoming edges in this directed graph.
• The properties of the matrix guarantee a unique champion based on the given rules.

Space and Time Complexity

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

Solution

To find the champion team, we can utilize a two-pointer approach, iterating through the teams to determine which team remains as the strongest contender. The algorithm works as follows:

1. Start with the first team and compare it with others.
2. If a team is stronger than the current champion, update the champion to this stronger team.
3. Continue this process until all teams have been compared.
4. The last team remaining as a potential champion is the actual champion.

This approach only requires a single pass through the teams, thus achieving O(n) time complexity.

Code Solutions