Problem Definition

Given an n x n adjacency matrix grid representing a tournament among n teams, where grid[i][j] = 1 indicates team i is stronger than team j, the objective is to identify the champion. A champion is defined as a team that is not weaker than any other team. Due to the transitive property of the strengths, there is guaranteed to be a single champion.

Quadratic Approach: Column Inspection

A champion team c implies that no other team beats c. In the matrix representation, this corresponds to column c containing only zeros (excluding the diagonal entry grid[c][c]).

We can iterate through every column. For a specific column index col, we scan all rows. If we find any grid[row][col] == 1, it means team row beats team col, disqualifying col. If the scan completes without finding a 1, then col is the champion.

Complexity Analysis: In the worst case, we inspect every cell in the matrix, resulting in O(n^2) time complexity. The algorithm uses constant extra space O(1).

int findChampionBruteForce(const vector<vector<int>>& matchResults) {
    int totalTeams = matchResults.size();
    for (int col = 0; col < totalTeams; ++col) {
        bool isUndefeated = true;
        for (int row = 0; row < totalTeams; ++row) {
            // Ignore self-comparison
            if (row != col && matchResults[row][col] == 1) {
                isUndefeated = false;
                break;
            }
        }
        if (isUndefeated) {
            return col;
        }
    }
    return -1; // Should not be reached given problem constraints
}

def find_champion_brute(matrix):
    n = len(matrix)
    for candidate in range(n):
        defeated = False
        for opponent in range(n):
            if candidate != opponent and matrix[opponent][candidate]:
                defeated = True
                break
        if not defeated:
            return candidate
    return -1

Linear Approach: Single Pass Optimization

The transitive nature of the team strengths allows for a more efficient solution. We can determine the champion by simulating a bracket-style comparison.

Initialize currentBest = 0. Iterate through the remaining teams from 1 to n-1. For each team i, compare it with currentBest. If grid[i][currentBest] == 1, it means team i beats currentBest, so we update currentBest = i. If grid[i][currentBest] == 0, currentBest remains unchanged as it is stronger than i. By the end of the loop, currentBest will hold the index of the strongest team.

Complexity Analysis: This method only requires a single pass through the list of teams, achieving O(n) time complexity. Space complexity remains O(1).

int findChampionOptimized(const vector<vector<int>>& matchResults) {
    int championIndex = 0;
    int totalTeams = matchResults.size();
    
    for (int challenger = 1; challenger < totalTeams; ++challenger) {
        // If challenger defeats the current champion, update champion
        if (matchResults[challenger][championIndex] == 1) {
            championIndex = challenger;
        }
    }
    
    return championIndex;
}

def find_champion_optimized(matrix):
    champion = 0
    n = len(matrix)
    
    for i in range(1, n):
        # If team 'i' beats the current 'champion', 'i' becomes the new champion
        if matrix[i][champion]:
            champion = i
            
    return champion