LeetCode Problem 2924

Difficulty: 🟡 Medium
Topics: Graph Theory

Solution

LeetCode 2924 - Find Champion II

Problem Understanding

This problem models a tournament as a directed acyclic graph (DAG). Each node represents a team, and each directed edge u -> v means team u is stronger than team v.

A team is considered the champion if no other team is stronger than it. In graph terminology, that means the node has no incoming edges. Every incoming edge represents another team that is stronger.

We are given:

• n, the number of teams labeled from 0 to n - 1
• edges, where each edge [u, v] means u is stronger than v

We must determine whether there is exactly one champion. If there is exactly one team with no incoming edges, return its index. Otherwise, return -1.

The constraints are relatively small, with n ≤ 100, but the goal is to recognize the graph property that directly identifies the champion.

The problem also guarantees several important properties:

• The graph is a DAG.
• If a is stronger than b, then b cannot be stronger than a.
• Strength relationships are transitive.

These guarantees ensure the graph represents a valid hierarchy of strength.

Several edge cases are worth considering:

• A graph with a single node and no edges. That node is automatically the champion.
• Multiple disconnected components. There may be multiple nodes with no incoming edges, which means there is no unique champion.
• A graph with no edges at all. Every node has indegree zero, so the answer is -1 unless n = 1.
• A graph where exactly one node has indegree zero. That node must be the unique champion.

Approaches

Brute Force

A straightforward approach is to examine every node and determine whether any other node is stronger than it.

For each node, we could scan all edges and check whether the node ever appears as a destination. If it never appears as a destination, then it has no incoming edges and is a potential champion.

After checking all nodes, we count how many candidates exist.

This works because a node is a champion exactly when no edge points into it. However, for every node we scan all edges, leading to unnecessary repeated work.

Key Insight

A node's indegree directly tells us how many stronger teams exist.

Every edge u -> v contributes one incoming edge to v. Therefore:

• Champion ⇔ indegree is 0
• Unique champion ⇔ exactly one node has indegree 0

Instead of repeatedly scanning all edges for every node, we can compute indegrees once. After that, we simply count how many nodes have indegree zero.

This transforms the problem into a simple indegree-counting exercise.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(1)	For every node, scan all edges
Optimal	O(n + m)	O(n)	Compute indegrees once and count zero-indegree nodes

Algorithm Walkthrough

1. Create an array indegree of size n initialized to zero.
2. Traverse every edge [u, v].

For each edge, increment indegree[v] because v has one more stronger team pointing to it. 3. After processing all edges, scan the indegree array. 4. Count how many nodes have indegree equal to zero.

These nodes have no stronger teams and are therefore champion candidates. 5. If exactly one node has indegree zero, return that node. 6. Otherwise, return -1 because there is either no champion or multiple possible champions.

Why it works

The key invariant is that indegree[i] always equals the number of teams stronger than team i.

A champion is defined as a team with no stronger teams. Therefore, champions correspond exactly to nodes with indegree zero.

If there is exactly one such node, it is the unique champion. If there are multiple such nodes, then multiple teams satisfy the champion condition, so the answer must be -1.

Python Solution

from typing import List

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        indegree = [0] * n

        for _, v in edges:
            indegree[v] += 1

        champion = -1

        for team in range(n):
            if indegree[team] == 0:
                if champion != -1:
                    return -1
                champion = team

        return champion

The implementation begins by creating an indegree array. Each position corresponds to a team, and the value stores how many incoming edges that team has.

Next, we process every edge. Since an edge u -> v means u is stronger than v, we increment the indegree of v.

After building the indegree array, we scan all teams. Whenever we find a team whose indegree is zero, it is a champion candidate.

The variable champion stores the first candidate found. If another zero-indegree node is encountered later, we immediately know there is more than one candidate and return -1.

If the scan finishes with exactly one candidate, that candidate is returned.

Go Solution

func findChampion(n int, edges [][]int) int {
	indegree := make([]int, n)

	for _, edge := range edges {
		v := edge[1]
		indegree[v]++
	}

	champion := -1

	for team := 0; team < n; team++ {
		if indegree[team] == 0 {
			if champion != -1 {
				return -1
			}
			champion = team
		}
	}

	return champion
}

The Go implementation follows the exact same logic as the Python version.

A slice is used to store indegrees. Since the constraints are small and indegree values never exceed n - 1, integer overflow is not a concern. Go slices are automatically initialized to zero values, making them convenient for indegree counting.

Worked Examples

Example 1

Input

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

Step 1: Initialize indegrees

Team	Indegree
0	0
1	0
2	0

Step 2: Process edges

Process [0,1]

Team	Indegree
0	0
1	1
2	0

Process [1,2]

Team	Indegree
0	0
1	1
2	1

Step 3: Find zero-indegree nodes

Team	Indegree	Candidate?
0	0	Yes
1	1	No
2	1	No

Only team 0 has indegree zero.

Answer

0

Example 2

Input

n = 4
edges = [[0,2],[1,3],[1,2]]

Step 1: Initialize indegrees

Team	Indegree
0	0
1	0
2	0
3	0

Step 2: Process edges

Process [0,2]

Team	Indegree
0	0
1	0
2	1
3	0

Process [1,3]

Team	Indegree
0	0
1	0
2	1
3	1

Process [1,2]

Team	Indegree
0	0
1	0
2	2
3	1

Step 3: Find zero-indegree nodes

Team	Indegree	Candidate?
0	0	Yes
1	0	Yes
2	2	No
3	1	No

There are two candidates, 0 and 1.

Answer

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	One pass over all edges and one pass over all nodes
Space	O(n)	Indegree array stores one value per node

The algorithm processes each edge exactly once while constructing the indegree array. It then scans all nodes once to count zero-indegree candidates. Therefore the total running time is linear in the size of the graph, O(n + m). The only extra memory used is the indegree array of size n.

Test Cases

from typing import List

s = Solution()

assert s.findChampion(3, [[0, 1], [1, 2]]) == 0  # Example 1

assert s.findChampion(4, [[0, 2], [1, 3], [1, 2]]) == -1  # Example 2

assert s.findChampion(1, []) == 0  # Single team

assert s.findChampion(2, []) == -1  # Two isolated teams

assert s.findChampion(3, [[0, 1]]) == -1  # Two zero-indegree nodes

assert s.findChampion(4, [[0, 1], [0, 2], [0, 3]]) == 0  # One dominant team

assert s.findChampion(5, [[0, 1], [1, 2], [2, 3], [3, 4]]) == 0  # Chain

assert s.findChampion(5, [[0, 2], [1, 2], [3, 4]]) == -1  # Multiple sources

assert s.findChampion(3, [[0, 1], [0, 2]]) == 0  # Star graph

assert s.findChampion(4, [[2, 0], [2, 1], [2, 3]]) == 2  # Champion not node 0

Test Summary

Test	Why
n=3, [[0,1],[1,2]]	Provided example with unique champion
n=4, [[0,2],[1,3],[1,2]]	Provided example with multiple candidates
n=1, []	Smallest possible input
n=2, []	No edges, multiple champions
n=3, [[0,1]]	Disconnected graph with multiple sources
n=4, [[0,1],[0,2],[0,3]]	One team dominates everyone
n=5 chain graph	Long linear hierarchy
n=5 disconnected components	Multiple zero-indegree nodes
Star graph	Single source with many outgoing edges
Champion not equal to node 0	Ensures logic does not assume ordering

Edge Cases

Single Team Tournament

When n = 1 and there are no edges, the only team has no stronger team. A common mistake is to assume at least one edge exists. The implementation correctly initializes indegree to [0], finds exactly one zero-indegree node, and returns 0.

No Edges with Multiple Teams

If n > 1 and edges is empty, every team has indegree zero. There is no unique champion because multiple teams satisfy the champion condition. The implementation detects a second zero-indegree node during the scan and immediately returns -1.

Multiple Disconnected Components

Consider a graph such as [[0,1],[2,3]]. Teams 0 and 2 both have indegree zero. Even though each component has a local strongest team, the tournament as a whole does not have a unique champion. The implementation correctly counts multiple zero-indegree nodes and returns -1.

Champion Is Not Team 0

Some incorrect solutions assume the champion must be the smallest-indexed node or the first node encountered. For example, in [[2,0],[2,1],[2,3]], team 2 is the only node with indegree zero. The algorithm relies solely on indegree counts, so it correctly returns 2.

Dense DAG

A graph may contain many edges, approaching n * (n - 1) / 2. The algorithm still processes each edge exactly once and remains efficient. Since only indegree counts are stored, memory usage remains linear in the number of nodes.