Find Champion II

Easy
930.

Find Champion II

Find Champion II is an easy coding problem on graph, asked in Amazon, Google and Wipro interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number}
 */
var findChampion = function(n, edges) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Champion II — Solution in Python, Java & C++

Find Champion II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on graph.

Find Champion II is an easy coding problem on graph, asked in Amazon, Google and Wipro interviews.

  • Difficulty: Easy
  • Topics: Graph
  • Asked at: Amazon, Google, Wipro
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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.

Hints for Find Champion II

  1. Hint 1

    "No team is stronger than it" means no edge points into it.

  2. Hint 2

    Count the in-degree of every node.

  3. Hint 3

    Exactly one node of in-degree zero gives the answer; zero or several give -1.

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

Java

public static int findChampion(int n, int[][] edges) {
    int[] indeg = new int[n];
    for (int[] e : edges) indeg[e[1]]++;
    int champ = -1;
    for (int i = 0; i < n; i++) {
        if (indeg[i] != 0) continue;
        if (champ >= 0) return -1;
        champ = i;
    }
    return champ;
}

C++

int findChampion(int n, vector<vector<int>>& edges) {
    vector<int> indeg(n, 0);
    for (auto& e : edges) indeg[e[1]]++;
    int champ = -1;
    for (int i = 0; i < n; i++) {
        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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 107 graph problems · the whole catalogue

Learn the technique: Graph Data Structure