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
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].
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 <= 100m == edges.length0 <= m <= n * (n - 1) / 2edges[i].length == 20 <= edge[i][j] <= n - 1edges[i][0] != edges[i][1]a is stronger than team b, team b is not stronger than team a.a is stronger than team b and team b is stronger than team c, then team a is stronger than team c.In this approach, we calculate the in-degree for each node in the graph. The in-degree of a node is the number of edges that point to it. If a node has an in-degree of 0, it means no other node (team in this case) is stronger than it, making it a candidate for the champion. If exactly one such node exists, it is the unique champion. Otherwise, we return -1.
This C code snippet creates an array to store the in-degree of each team. It iterates over the edges, updating the in-degree of destination nodes. Finally, it checks for nodes with an in-degree of 0. If there's exactly one, it returns this as the champion.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges. Space Complexity: O(n), as we store the in-degree of each node.
This approach uses topological sorting to find the last node in the order, presuming no other nodes are stronger. If multiple final nodes exist in the topological order, it implies multiple candidates, hence no unique champion can be determined.
This C implementation uses DFS for topological sorting to find the potential champion, verifying it by checking if it's stronger than all other remaining teams.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m). Space Complexity: O(n^2) due to adjacency matrix used for simplicity.
| Approach | Complexity |
|---|---|
| In-degree Tracking | Time Complexity: O(n + m), where n is the number of nodes and m is the number of edges. Space Complexity: O(n), as we store the in-degree of each node. |
| Topological Sorting | Time Complexity: O(n + m). Space Complexity: O(n^2) due to adjacency matrix used for simplicity. |
Find Champion II - Leetcode 2924 - Python • NeetCodeIO • 5,976 views views
Watch 9 more video solutions →Practice Find Champion II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor