Find Champion II

medium graph indegree

Problem

There are n teams numbered 0 to n − 1 in a tournament, given as a directed acyclic graph. A directed edge u → v means team u is stronger than team v. Team a is the champion if no other team is stronger than a. Return the champion's number, or -1 if the champion is not unique.

"No team is stronger than a" means no edge points into a — that is, a has in-degree 0. So count every node's in-degree; if exactly one node has in-degree 0 it is the champion, and if two or more do, the answer is ambiguous and we return -1.

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

Output0

In-degrees are [0, 1, 1]. Only team 0 has in-degree 0, so it is the unique champion.

edges (u,v; ...) directed u stronger than v

def find_champion(n, edges):
    indeg = [0] * n
    for u, v in edges:
        indeg[v] += 1
    champion = -1
    count = 0
    for i in range(n):
        if indeg[i] == 0:
            champion = i
            count += 1
    return champion if count == 1 else -1

function findChampion(n, edges) {
  const indeg = new Array(n).fill(0);
  for (const [u, v] of edges) {
    indeg[v]++;
  }
  let champion = -1;
  let count = 0;
  for (let i = 0; i < n; i++) {
    if (indeg[i] === 0) {
      champion = i;
      count++;
    }
  }
  return count === 1 ? champion : -1;
}

class Solution {
    public int findChampion(int n, int[][] edges) {
        int[] indeg = new int[n];
        for (int[] e : edges) {
            indeg[e[1]]++;
        }
        int champion = -1;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                champion = i;
                count++;
            }
        }
        return count == 1 ? champion : -1;
    }
}

class Solution {
public:
    int findChampion(int n, vector<vector<int>>& edges) {
        vector<int> indeg(n, 0);
        for (auto& e : edges) {
            indeg[e[1]]++;
        }
        int champion = -1;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                champion = i;
                count++;
            }
        }
        return count == 1 ? champion : -1;
    }
};

Explanation

The whole problem reduces to one observation: a champion is a team that nobody beats. In graph terms, an edge u → v records that u beats v, so "nobody beats team a" simply means no arrow lands on a — its in-degree is 0.

We make an indeg array of size n, all zeros. Then we walk through every edge [u, v] and increment indeg[v], because that edge is one team beating v.

After counting, we scan the nodes. Every node with indeg == 0 is a candidate champion. We remember the last such node and how many we have seen.

If exactly one node has in-degree 0, that node is the unique, undisputed champion. If two or more do, then neither can be proven strongest over the other, so the champion is not unique and we return -1. (The problem guarantees the graph is acyclic, so at least one such node always exists.)

Worked example: edges [[0,1],[1,2]] give in-degrees [0, 1, 1]. Only node 0 scores 0, the count is 1, so the answer is 0.

Time: O(V + E) Space: O(V)