Watch 6 video solutions for Find Champion I, a easy level problem involving Array, Matrix. This walkthrough by Prakhar Agrawal has 720 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Example 1:
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:
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.lengthn == grid[i].length2 <= n <= 100grid[i][j] is either 0 or 1.i grid[i][i] is 0.i, j that i != j, grid[i][j] != grid[j][i].a is stronger than team b and team b is stronger than team c, then team a is stronger than team c.Problem Overview: You are given an n x n tournament matrix where grid[i][j] = 1 means team i beats team j. The champion is the team that is not beaten by any other team. In graph terms, it is the node with zero incoming edges in a directed comparison matrix.
Approach 1: Naive Method with Grid Traversal (Time: O(n2), Space: O(1))
Scan the matrix column by column. If any grid[j][i] == 1, team j beats team i, so i cannot be the champion. For each team, iterate through all other teams and check if someone defeats it. The first team whose column contains only zeros (excluding itself) is the champion. This approach directly uses the tournament matrix representation and performs a full verification for every candidate.
The method is straightforward and mirrors the problem definition. However, it performs redundant checks because every candidate scans the entire column, leading to O(n^2) time. It works well for small inputs or when clarity is more important than micro‑optimizations.
Approach 2: Efficient Two-Pass Verification (Time: O(n), Space: O(1))
Instead of checking every team fully, eliminate non-champions while scanning once. Start with a candidate champ = 0. Iterate through teams from 1 to n-1. If grid[champ][i] == 0, the current champion loses to i, so update champ = i. Otherwise, i cannot be the champion because champ beats it.
After this pass, only one possible champion remains. Perform a second pass to verify that no team beats this candidate by checking grid[j][champ]. If all values are zero, the candidate is the champion. This technique treats the matrix like a directed comparison graph and progressively removes losing nodes.
The elimination idea avoids repeated scans and reduces the work to linear time. Only simple index comparisons are required, making the approach efficient even when the matrix is large. The underlying data structure is still a 2D array/matrix, but the algorithm behaves similarly to finding a node with zero in-degree in a graph.
Recommended for interviews: Start by explaining the naive column check because it directly models the problem definition. Then optimize using the two-pass elimination method. Interviewers usually expect the linear-time candidate elimination since it demonstrates reasoning about dominance relationships instead of brute-force scanning.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Method with Grid Traversal | O(n^2) | O(1) | Best for understanding the problem definition or when matrix size is small |
| Efficient Two-Pass Verification | O(n) | O(1) | Preferred in interviews and large inputs; eliminates non-champions in a single scan |