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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find Champion II

Number: 3189

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a tournament represented as a Directed Acyclic Graph (DAG) with n teams (nodes) and edges that indicate a “stronger-than” relation, find the unique champion team. A team is a champion if no other team is stronger than it (i.e. no incoming edge). Return the team number if there is a unique champion, otherwise return -1.

Key Insights

  • A team is a champion if and only if it has no incoming edges.
  • In the graph, an edge from team a to team b means a is stronger than b.
  • Calculate the in-degree for every node; only nodes with in-degree 0 satisfy the condition.
  • If more than one team has in-degree 0, there is no unique champion.

Space and Time Complexity

Time Complexity: O(n + m), where n is the number of teams and m is the number of edges. Space Complexity: O(n) for storing the in-degree of each team.

Solution

  • We initialize an array (or map) to count the in-degree of every team.
  • Iterate over all given edges; for each edge [u, v] increment the in-degree of team v because team u is stronger than team v.
  • After processing all edges, scan through the in-degree list.
  • If exactly one team has an in-degree of zero, that team is the champion; otherwise, if there are multiple teams with an in-degree of zero, then a unique champion does not exist and return -1.
  • This simple approach leverages fundamental graph in-degree computation and works efficiently given the problem constraints.

Code Solutions

# Python implementation for Find Champion II

def findChampion(n, edges):
    # Initialize in-degree list with zeros for each team
    in_degree = [0] * n

    # Process each edge and update in-degrees
    for u, v in edges:
        # u is stronger than v, so increase in-degree of v
        in_degree[v] += 1

    champion = -1  # default champion value
    # Check which team(s) have zero in-degree
    for team in range(n):
        if in_degree[team] == 0:
            # If a champion candidate already found, then not unique champion
            if champion != -1:
                return -1
            champion = team

    return champion

# Example usage:
# n = 3, edges = [[0,1],[1,2]]
# Expected output: 0
print(findChampion(3, [[0,1],[1,2]]))
← Back to All Questions