# Find Champion I
**Difficulty:** EASY
[External](https://leetcode.com/problems/find-champion-i)
Canonical: https://scaleengineer.com/dsa/problems/find-champion-i
**Data structures:** Array, Matrix
---
## 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._

**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.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`.

# Approaches
## Brute-Force by Checking Defeats
This approach iterates through every team and checks if it meets the definition of a champion. A team is a champion if no other team is stronger than it. We can verify this for each team directly by checking if it has been defeated by any other team.
**Time:** O(n^2), where `n` is the number of teams. In the worst-case scenario, we might have to check almost all pairs of teams. The outer loop runs up to `n` times, and the inner loop also runs `n` times. · **Space:** O(1), as we only use a few variables to keep track of the loops and the defeated status, not dependent on the input size `n`.
**Pros:** Straightforward and easy to understand, directly translating the problem definition into code.
**Cons:** Not the most efficient solution. The time complexity is quadratic, which can be slow for a very large number of teams (though acceptable for the given constraints).
### Explanation
The algorithm systematically checks each team from `0` to `n-1` to see if it's a champion.
For a given team `i`, we iterate through all other teams `j`. If we find any team `j` that is stronger than team `i` (i.e., `grid[j][i] == 1`), we know that team `i` cannot be the champion. In this case, we can stop checking for team `i` and move on to the next potential champion, `i+1`.
If we complete the inner loop for team `i` without finding any team that is stronger, it means team `i` is undefeated and is, therefore, the champion. The problem guarantees that a unique champion exists, so we can return `i` as soon as we find it.
```java
class Solution {
    public int findChampion(int[][] grid) {
        int n = grid.length;
        for (int i = 0; i < n; i++) {
            boolean isDefeated = false;
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                // If team j is stronger than team i
                if (grid[j][i] == 1) {
                    isDefeated = true;
                    break; // Team i is not a champion, check next team
                }
            }
            // If after checking all other teams, no one defeated team i
            if (!isDefeated) {
                return i; // Team i is the champion
            }
        }
        return -1; // Should not be reached as a champion always exists
    }
}
```
### Algorithm
- Iterate through each team `i` from `0` to `n-1`.
- For each team `i`, assume it is not defeated by setting a flag, e.g., `isDefeated = false`.
- Start a nested loop to iterate through every other team `j` from `0` to `n-1`.
- If `i` is the same as `j`, skip the comparison.
- Check if team `j` is stronger than team `i` by looking at `grid[j][i]`. If `grid[j][i] == 1`, it means team `i` is defeated. Set `isDefeated = true` and break the inner loop.
- After the inner loop, if `isDefeated` is still `false`, it means no team could defeat team `i`. Thus, `i` is the champion. Return `i`.

## Single Pass Elimination
A more efficient approach is to find the champion in a single pass. We can maintain a candidate for the champion and update it as we iterate through the teams. The key insight is that if a team `i` defeats our current candidate, the old candidate can be discarded, and `i` becomes the new candidate.
**Time:** O(n), where `n` is the number of teams. We iterate through the list of teams only once. · **Space:** O(1), as we only use a single extra variable to store the champion candidate.
**Pros:** Optimal time complexity, making it very fast.; Simple implementation with a single loop.
**Cons:** The correctness of the algorithm relies on the transitivity property of the tournament, which might not be immediately obvious without careful thought.
### Explanation
This optimized algorithm leverages the transitivity property of the tournament (`if a > b and b > c, then a > c`).
We start by assuming team `0` is the champion and store it in a `championCandidate` variable. Then, we iterate through the remaining teams from `1` to `n-1`.
For each team `i`, we compare it with our current `championCandidate`.
- If team `i` is stronger than `championCandidate` (i.e., `grid[i][championCandidate] == 1`), it means our current candidate is not the true champion. Team `i` is a better candidate, so we update `championCandidate = i`. Due to transitivity, any team that `championCandidate` was stronger than is also weaker than the new candidate `i`.
- If team `i` is weaker than `championCandidate`, then `i` cannot be the champion, and we can safely discard it and keep our current `championCandidate`.
After iterating through all the teams, the final `championCandidate` will be the one that was not defeated by any subsequent team in the pass. This process guarantees finding the single unique champion.
```java
class Solution {
    public int findChampion(int[][] grid) {
        int n = grid.length;
        int championCandidate = 0;
        for (int i = 1; i < n; i++) {
            // If team i is stronger than the current candidate
            if (grid[i][championCandidate] == 1) {
                // Team i becomes the new candidate
                championCandidate = i;
            }
        }
        return championCandidate;
    }
}
```
### Algorithm
- Initialize a variable `championCandidate` with the index of the first team, `0`.
- Iterate through the teams from `i = 1` to `n-1`.
- In each iteration, check if team `i` is stronger than the current `championCandidate` by checking `grid[i][championCandidate]`.
- If `grid[i][championCandidate] == 1`, update `championCandidate` to `i`.
- After the loop completes, the value stored in `championCandidate` is the index of the champion team. Return `championCandidate`.

# Solutions
### Java

```java
class Solution { public int findChampion ( int [][] grid ) { int n = grid . length ; for ( int i = 0 ;; ++ i ) { int cnt = 0 ; for ( int j = 0 ; j < n ; ++ j ) { if ( i != j && grid [ i ][ j ] == 1 ) { ++ cnt ; } } if ( cnt == n - 1 ) { return i ; } } } }
```

### CPP

```cpp
class Solution { public: int findChampion ( vector < vector < int >>& grid ) { int n = grid . size (); for ( int i = 0 ;; ++ i ) { int cnt = 0 ; for ( int j = 0 ; j < n ; ++ j ) { if ( i != j && grid [ i ][ j ] == 1 ) { ++ cnt ; } } if ( cnt == n - 1 ) { return i ; } } } };
```

### Python

```python
class Solution : def findChampion ( self , grid : List [ List [ int ]]) -> int : for i , row in enumerate ( grid ): if all ( x == 1 for j , x in enumerate ( row ) if i != j ): return i
```