⚡Flashcard Drill➔
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

  1. A champion must be stronger than everyone, so nobody is stronger than the champion.
  2. Therefore the champion has in-degree 0 in the "stronger than" DAG.
  3. If exactly one node has in-degree 0, it is the unique champion; otherwise there is no unique champion.
  4. 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] means u is stronger, so the edge is u -> 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems