Find Champion II

Find Champion II

What is this problem about?

Building on the first version, the Find Champion II coding problem moves from a matrix to a directed acyclic graph (DAG). You are given $n$ teams and a list of directed edges [u, v], meaning team $u$ is stronger than team $v$. A "champion" is a team that has no other team stronger than it. If there is exactly one such team, return its ID; otherwise, return -1.

Why is this asked in interviews?

Meta and Google ask this to evaluate your knowledge of Graph interview patterns, specifically In-degree calculation. It tests your ability to identify "source" nodes in a directed graph—nodes that have no incoming edges. It also evaluations your ability to handle ambiguity: if there are multiple teams with no superiors, there is no clear champion.

Algorithmic pattern used

This problem is solved by calculating the In-degree of every node.

1. Initialize an array in_degree of size $n$ with zeros.
2. For every edge [u, v], increment in_degree[v].
3. After processing all edges, count how many nodes have in_degree == 0.
4. If the count is exactly 1, return that node's ID.
5. If the count is 0 or $> 1$, return -1.

Example explanation

Teams: 3, Edges: [[0, 1], [1, 2]].

1. in_degree: Team 0 = 0, Team 1 = 1 (from 0), Team 2 = 1 (from 1).
2. Nodes with in-degree 0: {0}.
3. Exactly one champion. Result: 0.

Teams: 3, Edges: [[0, 2], [1, 2]].

1. in_degree: Team 0 = 0, Team 1 = 0, Team 2 = 2.
2. Nodes with in-degree 0: {0, 1}.
3. More than one source. Result: -1.

Common mistakes candidates make

• Using BFS/DFS: While traversals can find reachability, they are overkill for simply checking who has no "parents."
• Confusing in-degree and out-degree: Thinking the champion is the one who beats the most people (highest out-degree).
• Missing the "Only One" rule: Forgetting to return -1 if multiple source nodes exist.

Interview preparation tip

Source nodes (in-degree 0) and sink nodes (out-degree 0) are the starting and ending points of many graph algorithms like Topological Sort. Mastery of degree counting is a prerequisite for more advanced graph problems.