Problem

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

Given a 0-indexed 2D boolean matrix grid of size n * n. For all i, j that 0 <= i, j <= n - 1 and i != j team i is stronger than team j if grid[i][j] == 1, otherwise, team j is stronger than team i.

Team a will be the champion of the tournament if there is no team b that is stronger than team a.

Return the team that will be the champion of the tournament.

Examples

Example 1

1
2
3
4

Input: grid = [[0,1],[0,0]]
Output: 0
Explanation: There are two teams in this tournament.
grid[0][1] == 1 means that team 0 is stronger than team 1. So team 0 will be the champion.

Example 2

1
2
3
4
5
6

Input: grid = [[0,0,1],[1,0,1],[0,0,0]]
Output: 1
Explanation: There are three teams in this tournament.
grid[1][0] == 1 means that team 1 is stronger than team 0.
grid[1][2] == 1 means that team 1 is stronger than team 2.
So team 1 will be the champion.

Constraints

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

Solution

Method 1 – Row Dominance 1

Intuition

The champion is the team that is not beaten by any other team. In the grid, this means the row for the champion has all 1s (except the diagonal), i.e., the champion beats every other team.

Approach

  1. Iterate through each team (row in grid).
  2. For each team, check if all other entries in its row (except itself) are 1.
  3. If such a row is found, return its index as the champion.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
public:
    int findChampion(vector<vector<int>>& grid) {
        int n = grid.size();
        for (int i = 0; i < n; ++i) {
            bool champ = true;
            for (int j = 0; j < n; ++j) {
                if (i != j && grid[i][j] == 0) {
                    champ = false;
                    break;
                }
            }
            if (champ) return i;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

func findChampion(grid [][]int) int {
    n := len(grid)
    for i := 0; i < n; i++ {
        champ := true
        for j := 0; j < n; j++ {
            if i != j && grid[i][j] == 0 {
                champ = false
                break
            }
        }
        if champ {
            return i
        }
    }
    return -1
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    public int findChampion(int[][] grid) {
        int n = grid.length;
        for (int i = 0; i < n; i++) {
            boolean champ = true;
            for (int j = 0; j < n; j++) {
                if (i != j && grid[i][j] == 0) {
                    champ = false;
                    break;
                }
            }
            if (champ) return i;
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun findChampion(grid: Array<IntArray>): Int {
        val n = grid.size
        for (i in 0 until n) {
            var champ = true
            for (j in 0 until n) {
                if (i != j && grid[i][j] == 0) {
                    champ = false
                    break
                }
            }
            if (champ) return i
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def findChampion(self, grid: list[list[int]]) -> int:
        n = len(grid)
        for i in range(n):
            champ = True
            for j in range(n):
                if i != j and grid[i][j] == 0:
                    champ = False
                    break
            if champ:
                return i
        return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn find_champion(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        for i in 0..n {
            let mut champ = true;
            for j in 0..n {
                if i != j && grid[i][j] == 0 {
                    champ = false;
                    break;
                }
            }
            if champ {
                return i as i32;
            }
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    findChampion(grid: number[][]): number {
        const n = grid.length;
        for (let i = 0; i < n; i++) {
            let champ = true;
            for (let j = 0; j < n; j++) {
                if (i !== j && grid[i][j] === 0) {
                    champ = false;
                    break;
                }
            }
            if (champ) return i;
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), because we check every cell in the grid for each team.
  • 🧺 Space complexity: O(1), as only a few variables are used regardless of input size.