Problem Description

In a tournament with n teams, numbered from 0 to n-1, a n x n boolean matrix grid is providde. The value grid\[i\]\[j\] indicates the outcome of a match between team i and team j. If grid\[i\]\[j\] == 1, team i is considered stronger than team j. The task is to identify the champion team, which is defined as the team that no other team is stronger than.

Examples

Example 1

Input: grid = [[0,1],[0,0]]
Output: 0
Explanation: Team 0 is stronger than Team 1, making Team 0 the champion.

Example 2

Input: grid = [[0,0,1],[1,0,1],[0,0,0]]
Output: 1
Explanation: Team 1 is stronger than both Team 0 and Team 2, so Team 1 is the champion.

Approach

Method 1: Counting Wins

The champion team must have defeated every other team. This means its corresponding row in the grid matrix will contain n-1 ones (excluidng the diagonal element which is always 0). We can iterate through each row, count the number of ones, and return the index of the row with n-1 wins.

Method 2: Tournament Elimination

We can simulate a "king of the hill" scenario. Start with an initial champion, say team 0. For each subsequent team, check if the current champion is stronger. If the current champion loses (i.e., grid\[current\_champion\]\[opponent\] == 0), the opponent becomes the new champion. After iterating through all teams, the remaining champion is the winner.

Solutions

C++ - Counting Wins

class Solution {
public:
    int findChampion(vector<vector>>& grid) {
        int num_teams = grid.size();
        for (int team = 0; team < num_teams; ++team) {
            int total_wins = 0;
            for (int match = 0; match < num_teams; ++match) {
                if (grid[team][match] == 1) {
                    total_wins++;
                }
            }
            if (total_wins == num_teams - 1) {
                return team;
            }
        }
        return -1; // As per problem constraints, a champion always exists.
    }
};</vector>

C++ - Tournament Elimination

class Solution {
public:
    int findChampion(vector<vector>>& grid) {
        int current_champion = 0;
        int num_teams = grid.size();
        for (int opponent = 1; opponent < num_teams; ++opponent) {
            if (grid[current_champion][opponent] == 0) {
                current_champion = opponent;
            }
        }
        return current_champion;
    }
};</vector>