#2924

Medium

auto_awesomeGraph-driven solution strategy

LeetCode Problem Workspace

Find Champion II

Identify the strongest team in a tournament DAG using graph-driven logic, ensuring correct handling of in-degree zero champions efficiently.

graph

Problem Statement

You are given n teams numbered from 0 to n - 1, forming a tournament represented as a directed acyclic graph. Each directed edge [a, b] indicates that team a is stronger than team b.

Write a function that receives n and edges, and returns the index of the champion team if one exists uniquely. If there is no single team stronger than all others, return -1.

Examples

Example 1

Input: n = 3, edges = [[0,1],[1,2]]

Output: 0

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

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 <= 100
m == edges.length
0 <= m <= n * (n - 1) / 2
edges[i].length == 2
0 <= edge[i][j] <= n - 1
edges[i][0] != edges[i][1]
The input is generated such that if team a is stronger than team b, team b is not stronger than team a.
The input is generated such that if team a is stronger than team b and team b is stronger than team c, then team a is stronger than team c.

Solution Approach

Compute in-degrees

For each team, count the number of edges pointing to it. Teams with zero in-degree are candidates for champion because no team is stronger than them.

Identify unique champion

After computing in-degrees, check if there is exactly one team with zero in-degree. If so, return its index; otherwise, return -1 as multiple teams or none cannot be a single champion.

Time and space optimization

Iterate edges once to compute in-degrees in O(N + M) time and use O(N) space for the in-degree array, ensuring efficient handling of up to 100 teams.

Complexity Analysis

Metric	Value
Time	O(N + M)
Space	O(N)

The algorithm traverses all edges and nodes once, giving O(N + M) time. The in-degree array stores counts for each team, using O(N) space.

What Interviewers Usually Probe

Expect clear reasoning on why only zero in-degree nodes qualify as champions.
Watch for handling multiple zero in-degree teams and returning -1 correctly.
Check that candidate selection does not exceed linear time relative to nodes and edges.

Common Pitfalls or Variants

Common pitfalls

Forgetting that multiple zero in-degree teams mean no unique champion.
Assuming the node with the largest index or edge count is the champion.
Ignoring edge cases with empty edge lists where any team could be champion.

Follow-up variants

Finding the weakest team by identifying nodes with zero out-degree instead of zero in-degree.
Handling weighted edges to determine dominance when strengths are quantified.
Detecting cycles in the input graph which would invalidate the DAG assumption.

FAQ

What is the main pattern used in Find Champion II?

The main pattern is graph-driven: compute in-degrees in the DAG and identify the unique node with zero in-degree as the champion.

What should I return if multiple teams have zero in-degree?

Return -1 because the problem specifies that only a unique champion should be returned.

Can the graph contain cycles in Find Champion II?

No, the input is guaranteed to be a directed acyclic graph to maintain valid strength relationships.

What is the time complexity of the optimal solution?

The solution runs in O(N + M) time, where N is the number of teams and M is the number of edges.

Why is in-degree important in this problem?

A champion must have no stronger team, which corresponds to having zero in-degree in the DAG representation.

terminal

Solution

Solution 1: Counting In-degrees

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.

1

2

3

4

5

6

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        indeg = [0] * n
        for _, v in edges:
            indeg[v] += 1
        return -1 if indeg.count(0) != 1 else indeg.index(0)

Solution 2

#### TypeScript

1

2

3

4

5

6

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        indeg = [0] * n
        for _, v in edges:
            indeg[v] += 1
        return -1 if indeg.count(0) != 1 else indeg.index(0)

Continue Practicing

#2959 number of possible sets of closing branches #2876 count visited nodes in a directed graph #2976 minimum cost to convert string i