We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Champion II

Difficulty: Medium

Problem Description

Given n teams numbered from 0 to n - 1 in a tournament represented as a directed acyclic graph (DAG), where each directed edge indicates that one team is stronger than another, return the champion team (the team that is not weaker than any other team) if there is a unique champion. Otherwise, return -1.

Key Insights

  • The champion team is the team that has no incoming edges in the DAG.
  • If more than one team has no incoming edges, there is no unique champion.
  • The problem can be solved by counting the incoming edges for each team.

Space and Time Complexity

Time Complexity: O(n + m)
Space Complexity: O(n)

Solution

To solve the problem, we can use an array to keep track of the number of incoming edges (in-degrees) for each team. We'll iterate over the edges to populate this array. After that, we'll check how many teams have an in-degree of zero. If exactly one team has zero incoming edges, that team is the champion; otherwise, we return -1.

Code Solutions

def findChampion(n, edges):
    # Create an array to count incoming edges
    in_degree = [0] * n
    
    # Count the in-degrees for each team
    for u, v in edges:
        in_degree[v] += 1
    
    # Find the team(s) with zero incoming edges
    champions = [i for i in range(n) if in_degree[i] == 0]
    
    # If exactly one team has zero in-degree, return it; otherwise, return -1
    return champions[0] if len(champions) == 1 else -1
← Back to All Questions