Watch 10 video solutions for Find Champion II, a medium level problem involving Graph. This walkthrough by NeetCodeIO has 6,667 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |