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.Problem Overview: You are given n teams and a list of directed edges where [a, b] means team a beats team b. The champion is the only team that no other team beats. In graph terms, this is the node with zero incoming edges. If more than one such node exists, or none exists, there is no clear champion and the result is -1.
Approach 1: In-degree Tracking (O(n + m) time, O(n) space)
Treat the input as a directed graph with n nodes and m edges. Maintain an array indegree[n] initialized to zero. Iterate through every edge (u, v) and increment indegree[v]. After processing all edges, scan the array to count how many nodes have indegree == 0. If exactly one node has zero incoming edges, that node is the champion because no other team defeated it. If the count is greater than one or zero, return -1. This works because every defeated team must have at least one incoming edge. The approach is linear in the size of the graph and uses only a single pass over edges plus a scan of nodes. This is the simplest and most direct solution when working with a graph representation.
Approach 2: Topological Sorting (O(n + m) time, O(n + m) space)
Another way to reason about the champion is through topological sorting. Build an adjacency list and compute the in-degree of each node. Push every node with indegree == 0 into a queue. If more than one node enters the queue initially, multiple teams are undefeated and a unique champion does not exist. Otherwise, process nodes in topological order by removing them from the queue and reducing the in-degree of their neighbors. The first node processed represents the only node with zero incoming edges at the start, which identifies the champion candidate. If the initial queue contains more than one node, return -1. This approach mirrors standard graph traversal workflows used in DAG processing and is useful when you already need the graph structure for further processing.
Recommended for interviews: The in-degree tracking solution is what interviewers usually expect. It shows you understand how directed graphs encode dominance relationships and how to identify source nodes efficiently. Topological sorting demonstrates deeper graph knowledge, but it introduces extra structures that are unnecessary for this specific problem. Showing the simple in-degree observation first and then mentioning the topological sort interpretation signals strong problem-solving clarity.
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.
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.
Time Complexity: O(n + m). Space Complexity: O(n^2) due to adjacency matrix used for simplicity.
Based on the problem description, we only need to count the in-degrees of each node and record them in an array indeg. If only one node has an in-degree of 0, then this node is the champion; otherwise, there is no unique champion.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes.
Python
Java
C++
Go
TypeScript
JavaScript
TypeScript
JavaScript
| 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. |
| Counting In-degrees | — |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-degree Tracking | O(n + m) | O(n) | Best general solution when you only need to identify the node with zero incoming edges |
| Topological Sorting (Kahn's Algorithm) | O(n + m) | O(n + m) | Useful when performing broader DAG processing or when topological order is also required |
Find Champion II - Leetcode 2924 - Python • NeetCodeIO • 6,667 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