Find Champion II

Med

#2604Time: 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.

Data structures

Graph

Prompt

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] = [u_i, v_i] indicates that there is a directed edge from team u_i to team v_i 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 a₁, a₂, ..., a_n, a_n+1 such that node a₁ is the same node as node a_n+1, the nodes a₁, a₂, ..., a_n are distinct, and there is a directed edge from the node a_i to node a_i+1 for every i in the range [1, n].
A DAG is a directed graph that does not have any cycle.

Example 1:

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:

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

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int findChampion(int n, int[][] edges) {6        List<Integer> champions = new ArrayList<>();7        for (int i = 0; i < n; i++) {8            boolean isChampion = true;9            for (int[] edge : edges) {10                if (edge[1] == i) {11                    isChampion = false;12                    break;13                }14            }15            if (isChampion) {16                champions.add(i);17            }18        }19 20        if (champions.size() == 1) {21            return champions.get(0);22        } else {23            return -1;24        }25    }26}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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.

1class Solution {2    public int findChampion(int n, int[][] edges) {3        int[] inDegree = new int[n];4        for (int[] edge : edges) {5            // edge[1] is the weaker team, so its in-degree increases.6            inDegree[edge[1]]++;7        }8 9        int champion = -1;10        int championCount = 0;11        for (int i = 0; i < n; i++) {12            // A champion has an in-degree of 0.13            if (inDegree[i] == 0) {14                championCount++;15                champion = i;16            }17        }18 19        // If there is exactly one team with in-degree 0, it's the unique champion.20        if (championCount == 1) {21            return champion;22        } else {23            // Otherwise, there are multiple champions, so return -1.24            return -1;25        }26    }27}

Complexity

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.

Trade-offs

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).

Solutions

Solution

1class Solution {2public3  int findChampion(int n, int[][] edges) {4    int[] indeg = new int[n];5    for (var e : edges) {6      ++indeg[e[1]];7    }8    int ans = -1, cnt = 0;9    for (int i = 0; i < n; ++i) {10      if (indeg[i] == 0) {11        ++cnt;12        ans = i;13      }14    }15    return cnt == 1 ? ans : -1;16  }17}

1function 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 ; }

1class Solution {2public:3  int findChampion(int n, vector<vector<int>> &edges) {4    int indeg[n];5    memset(indeg, 0, sizeof(indeg));6    for (auto &e : edges) {7      ++indeg[e[1]];8    }9    int ans = -1, cnt = 0;10    for (int i = 0; i < n; ++i) {11      if (indeg[i] == 0) {12        ++cnt;13        ans = i;14      }15    }16    return cnt == 1 ? ans : -1;17  }18};

1class Solution:2    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)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem