Problem of The Day: Find Champion II

Problem Statement

Intuition

The problem involves finding a single node (the “champion”) that has a specific property: it must not be pointed to by any other node. This leads to the idea of tracking incoming connections to identify potential candidates for the champion.

Approach

1. Initialize In-Degree Map:

   • Create a dictionary to store the in-degree (number of incoming edges) for each node. Start with all nodes having an in-degree of 0.

2. Update In-Degree:

   • Iterate over the given edges and update the in-degree for each destination node.

3. Identify Candidate:

   • Traverse through the in-degree dictionary to find nodes with an in-degree of 0. These nodes are not pointed to by any other node and are potential candidates.

4. Validate Candidate:

   • If there are multiple nodes with an in-degree of 0 or no such nodes exist, return -1 as there is no unique champion.
   • Otherwise, return the single node with an in-degree of 0 as the champion.

Complexity

• Time Complexity:
  \(O(n + m)\), where \(n\) is the number of nodes and \(m\) is the number of edges. The \(O(n)\) comes from initializing the in-degree dictionary and traversing it, while \(O(m)\) is the cost of iterating over the edges.
• Space Complexity:
  \(O(n)\), for storing the in-degree dictionary.

Code

class Solution:
    def findChampion(self, n: int, edges: List[List[int]]) -> int:
        in_degree = {i: 0 for i in range(n)}
        for src, dst in edges:
            in_degree[dst] += 1

        q = deque()
        for node, degree in in_degree.items():
            if degree == 0:
                q.append(node)

        if len(q) > 1 or not q:
            return -1

        return q[0]

Editorial

In-degree Count

class Solution:
    def findChampion(self, n: int, edges: list[list[int]]) -> int:
        # Initialize the indegree array to track the number of incoming edges for each team
        indegree = [0] * n

        # Store the indegree of each team
        for edge in edges:
            indegree[edge[1]] += 1

        champ = -1
        champ_count = 0

        # Iterate through all teams to find those with an indegree of 0
        for i in range(n):
            # If the team can be a champion, store the team number and increment the count
            if indegree[i] == 0:
                champ_count += 1
                champ = i

        # If more than one team can be a champion, return -1, otherwise return the champion team number
        return champ if champ_count == 1 else -1