Find Champion II — Easy Problem & Solution

Problem statement

n teams form a directed acyclic graph: an edge [u, v] means team u is stronger than team v.

A team is the champion if no other team is stronger than it. Return the champion's index if there is exactly one, and -1 if there is none or more than one.

Example 1

Input: n = 3, edges = [[0,1],[1,2]]
Output: 0
Explanation: Nothing points at team 0.

Example 2

Input: n = 4, edges = [[0,2],[1,3],[1,2]]
Output: -1
Explanation: Both team 0 and team 1 have nothing above them.

Example 3

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

Constraints

• 1 <= n <= 100
• m == edges.length
• 0 <= m <= n * (n - 1) / 2
• edges[i].length == 2
• 0 <= edges[i][j] <= n - 1
• edges[i][0] != edges[i][1]
• The input is a directed acyclic graph with no repeated edges.

How to solve Find Champion II

The champion is a node with in-degree 0, so one pass over the edges and one pass over the nodes settles it.

Approach

1. Count indeg[v] for every edge [u, v].
2. Scan the nodes for in-degree zero.
3. Return the single such node, or -1 if the count is not exactly one.

Why it works

The graph being acyclic guarantees at least one node of in-degree zero, so -1 only ever comes from an ambiguous answer, never an absent one. A second such node means neither is comparable to the other, so no single team is above everything.

Complexity

• Time — O(n + m)
• Space — O(n)

Pitfalls

• Out-degree is not the test; a team with many wins may still lose to someone.
• Two zero-in-degree nodes must answer -1, not the first one found.
• A graph with no edges and n > 1 answers -1.

Reference solution

Python

from typing import List

def findChampion(n: int, edges: List[List[int]]) -> int:
    indeg = [0] * n
    for _, v in edges:
        indeg[v] += 1
    champ = -1
    for i in range(n):
        if indeg[i] != 0:
            continue
        if champ >= 0:
            return -1
        champ = i
    return champ

JavaScript

var findChampion = function(n, edges) {
    var indeg = [];
    for (var i = 0; i < n; i++) indeg.push(0);
    for (i = 0; i < edges.length; i++) indeg[edges[i][1]]++;
    var champ = -1;
    for (i = 0; i < n; i++) {
        if (indeg[i] !== 0) continue;
        if (champ >= 0) return -1;
        champ = i;
    }
    return champ;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More graph problems

• Find Champion I Easy
• Find if Path Exists in Graph Easy
• Find the Town Judge Easy
• Find Center of Star Graph Easy
• Minimum Time to Visit a Cell In a Grid Hard
• Checking Existence of Edge Length Limited Paths Hard