# Find Champion II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-champion-ii)
Canonical: https://scaleengineer.com/dsa/problems/find-champion-ii
**Data structures:** Graph
---
## Problem
There are `n` teams numbered from `0` to `n - 1` in a tournament; each team is also a node in a **DAG**.

You are given the integer `n` and a **0-indexed** 2D integer array `edges` of length `m` representing the **DAG**, where `edges[i] = [ui, vi]` indicates that there is a directed edge from team `ui` to team `vi` in the graph.

A directed edge from `a` to `b` in the graph means that team `a` is **stronger** than team `b` and team `b` is **weaker** than team `a`.

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 if there is a **unique** champion, otherwise, return_ `-1`_._

**Notes**

* A **cycle** is a series of nodes `a1, a2, ..., an, an+1` such that node `a1` is the same node as node `an+1`, the nodes `a1, a2, ..., an` are distinct, and there is a directed edge from the node `ai` to node `ai+1` for every `i` in the range `[1, n]`.
* A **DAG** is a directed graph that does not have any **cycle**.

**Example 1:**

![](https://assets.glich.co/dsa/find-champion-ii/image0.png)

**Input:** n = 3, edges = [[0,1],[1,2]]
**Output:** 0
**Explanation:** Team 1 is weaker than team 0. Team 2 is weaker than team 1. So the champion is team 0.

**Example 2:**

![](https://assets.glich.co/dsa/find-champion-ii/image1.png)

**Input:** n = 4, edges = [[0,2],[1,3],[1,2]]
**Output:** -1
**Explanation:** Team 2 is weaker than team 0 and team 1. Team 3 is weaker than team 1. But team 1 and team 0 are not weaker than any other teams. So the answer is -1.

**Constraints:**

* `1 <= n <= 100`
* `m == edges.length`
* `0 <= m <= n * (n - 1) / 2`
* `edges[i].length == 2`
* `0 <= edge[i][j] <= n - 1`
* `edges[i][0] != edges[i][1]`
* The input is generated such that if team `a` is stronger than team `b`, team `b` is not stronger than team `a`.
* 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 Iteration
This approach involves a straightforward, brute-force check. It iterates through every team one by one. For each team, it scans the entire list of matches (`edges`) to determine if there is any other team that is stronger. If no such stronger team is found after checking all matches, the team is considered a champion.
**Time:** O(n * m), where `n` is the number of teams and `m` is the number of edges. The outer loop runs `n` times, and for each team, the inner loop may run up to `m` times. · **Space:** O(n), where `n` is the number of teams. In the worst-case scenario (a graph with no edges), the `champions` list could store all `n` teams.
**Pros:** The logic is simple and directly follows the definition of a champion.; It's easy to implement without requiring complex data structures.
**Cons:** This approach is inefficient because it repeatedly scans the entire `edges` list for each team, leading to a higher time complexity.; For dense graphs where the number of edges `m` is large, the performance degradation is significant compared to more optimal solutions.
### Explanation
The algorithm maintains a list to store the identified champions. It loops through each team `i` from `0` to `n-1`. For each team `i`, it assumes it's a champion and then verifies this assumption by iterating through all the given `edges`. Inside the inner loop, for each edge `[u, v]`, it checks if the current team `i` is the weaker team (i.e., `v == i`). If `i` is found to be a weaker team, it cannot be a champion. A flag is set, and the inner loop (over edges) is terminated for the current team `i`. If the inner loop completes without finding any team stronger than `i`, then `i` is confirmed as a champion and is added to our list of champions. After checking all teams, the algorithm examines the size of the champion list. If the list contains exactly one team, that team's ID is returned. Otherwise, if there are zero or more than one champions, `-1` is returned.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int findChampion(int n, int[][] edges) {
        List<Integer> champions = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            boolean isChampion = true;
            for (int[] edge : edges) {
                if (edge[1] == i) {
                    isChampion = false;
                    break;
                }
            }
            if (isChampion) {
                champions.add(i);
            }
        }

        if (champions.size() == 1) {
            return champions.get(0);
        } else {
            return -1;
        }
    }
}
```
### Algorithm
- Initialize an empty list `champions` to store the IDs of champion teams.
- Iterate through each team `i` from `0` to `n-1`.
- For each team `i`, assume it's a champion by setting a flag `isChampion` to `true`.
- To verify this, iterate through every edge `[u, v]` in the `edges` list.
- If the current team `i` is the weaker team in an edge (i.e., `v == i`), it means another team `u` is stronger. Thus, `i` cannot be a champion. Set `isChampion` to `false` and break the inner loop over the edges.
- If the inner loop completes and `isChampion` remains `true`, it means no team is stronger than `i`. Add `i` to the `champions` list.
- After checking all teams, if the `champions` list contains exactly one element, return that element.
- Otherwise, return `-1`.

## In-Degree Counting
A more efficient approach defines a champion in graph terms: a node with an in-degree of zero. A team is a champion if no other team is stronger, which means there are no incoming edges to its corresponding node in the graph. This method calculates the in-degree for all teams and then identifies the unique team with an in-degree of zero.
**Time:** O(n + m), where `n` is the number of teams and `m` is the number of edges. We perform one pass over the `edges` array (O(m)) and one pass over the teams (O(n)). · **Space:** O(n), where `n` is the number of teams. This space is used for the `inDegree` array.
**Pros:** Highly efficient, with a linear time complexity relative to the size of the input (nodes + edges).; This is the optimal approach as it requires examining each node and edge only once.
**Cons:** Requires extra space proportional to the number of teams, which could be a consideration for extremely large `n` (though not an issue with the given constraints).
### Explanation
The core idea is that any team `v` that appears as the second element in an edge `[u, v]` has a stronger opponent `u` and thus cannot be a champion. This is equivalent to saying a champion node must have an in-degree of 0. We can calculate the in-degree for every team. An integer array, `inDegree`, of size `n` is initialized to all zeros. We iterate through the `edges` array just once. For each edge `[u, v]`, we increment the in-degree count for the weaker team `v`. After processing all the edges, the `inDegree` array holds the count of stronger opponents for each team. We then iterate through the `inDegree` array to find the champions. Any team `i` for which `inDegree[i]` is `0` is a champion. We count how many such champions exist. If the count is exactly one, we return that champion's ID. Otherwise, we return -1.

```java
class Solution {
    public int findChampion(int n, int[][] edges) {
        int[] inDegree = new int[n];
        for (int[] edge : edges) {
            // edge[1] is the weaker team, so its in-degree increases.
            inDegree[edge[1]]++;
        }

        int champion = -1;
        int championCount = 0;
        for (int i = 0; i < n; i++) {
            // A champion has an in-degree of 0.
            if (inDegree[i] == 0) {
                championCount++;
                champion = i;
            }
        }

        // If there is exactly one team with in-degree 0, it's the unique champion.
        if (championCount == 1) {
            return champion;
        } else {
            // Otherwise, there are multiple champions, so return -1.
            return -1;
        }
    }
}
```
### Algorithm
- Create an integer array `inDegree` of size `n` and initialize all its elements to `0`. This array will store the number of teams stronger than each team.
- Iterate through each edge `[u, v]` in the `edges` list once. For each edge, increment the in-degree of the weaker team `v` (i.e., `inDegree[v]++`).
- After populating the `inDegree` array, initialize a `champion` variable to `-1` and a `championCount` to `0`.
- Iterate through all teams `i` from `0` to `n-1`.
- If `inDegree[i]` is `0`, it means no team is stronger than team `i`, so it's a champion. Increment `championCount` and update `champion` to `i`.
- Finally, check `championCount`. If it is `1`, return the `champion`'s ID. Otherwise, return `-1`.

# Solutions
### Java

```java
class Solution {
public
  int findChampion(int n, int[][] edges) {
    int[] indeg = new int[n];
    for (var e : edges) {
      ++indeg[e[1]];
    }
    int ans = -1, cnt = 0;
    for (int i = 0; i < n; ++i) {
      if (indeg[i] == 0) {
        ++cnt;
        ans = i;
      }
    }
    return cnt == 1 ? ans : -1;
  }
}

```

### JavaScript

```javascript
function findChampion ( n , edges ) { const indeg = Array ( n ). fill ( 0 ); for ( const [ _ , v ] of edges ) { ++ indeg [ v ]; } let [ ans , cnt ] = [ - 1 , 0 ]; for ( let i = 0 ; i < n ; ++ i ) { if ( indeg [ i ] === 0 ) { ++ cnt ; ans = i ; } } return cnt === 1 ? ans : - 1 ; }
```

### CPP

```cpp
class Solution {
public:
  int findChampion(int n, vector<vector<int>> &edges) {
    int indeg[n];
    memset(indeg, 0, sizeof(indeg));
    for (auto &e : edges) {
      ++indeg[e[1]];
    }
    int ans = -1, cnt = 0;
    for (int i = 0; i < n; ++i) {
      if (indeg[i] == 0) {
        ++cnt;
        ans = i;
      }
    }
    return cnt == 1 ? ans : -1;
  }
};

```

### Python

```python
class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int: indeg = [0] * n for _, v in edges: indeg[v] += 1 return - 1 if indeg . count(0) != 1 else indeg . index(0)

```