Find Champion II — LeetCode 2924 Python Solution

The problem

There are n teams numbered from 0 to n - 1 in a tournament; each team is also a node in a DAG. You are given the integer n and a 0-indexed 2D integer array edges of length m representing the DAG, where edges[i] = [ui, vi] indicates that there is a directed edge from team ui to team vi in the graph.

Example

Input

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

Output

0

Explanation

Team 1 is weaker than team 0. Team 2 is weaker than team 1. So the champion is team 0.

Python solution

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)

Complexity

Pattern: Depth-First Search

Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 2924. Find Champion II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Graph.

The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.

Related problems