NeetCode #561LC-2924MediumGraphs
← Back to All Problems#561 · #2924 · Find Champion II(找到冠军 II)
📌 Problem Statement & Constraints
There are
n teams numbered 0..n-1 in a tournament. edges[i] = [u, v] means team u is stronger than team v. A team is the champion if it is stronger than every other team, directly or indirectly. Return the champion's number, or -1 if there is none or more than one. Constraints: 1 <= n <= 100, 0 <= edges.length <= n * (n - 1) / 2, the graph is a DAG.💡 Core Algorithmic Approaches
- A champion must be stronger than everyone, so nobody is stronger than the champion.
- Therefore the champion has in-degree 0 in the "stronger than" DAG.
- If exactly one node has in-degree 0, it is the unique champion; otherwise there is no unique champion.
- This reduces the whole problem to a degree count.
💻 Benchmark Python3 Implementation
class Solution:
def findChampion(self, n: int, edges: List[List[int]]) -> int:
indeg = [0] * n
for u, v in edges:
indeg[v] += 1 # someone is stronger than v
candidates = [i for i in range(n) if indeg[i] == 0]
return candidates[0] if len(candidates) == 1 else -1⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + E): one pass over the edges and one over the teams.
💾 Space Complexity
O(n) for the in-degree array.
⚠️ Interview Pitfalls & Follow-ups
- Assuming in-degree 0 is sufficient in any graph: it is sufficient here because the graph is a DAG, so a source reaches everything.
- Returning the first candidate without the uniqueness check: multiple sources means no unique champion.
- Reversing the edge direction:
[u, v]meansuis stronger, so the edge isu -> v. - Running a transitive closure: unnecessary given the DAG guarantee.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.