2924. Find Champion II

Problem Description

In this problem, we are dealing with a tournament involving n teams, where each team is represented as a node in a Directed Acyclic Graph (DAG). The 2D integer array edges defines the relationships between the teams in terms of their strength; if there is a directed edge from team a to team b (represented as [a, b]), it implies that team a is stronger than team b. The goal is to find which team is the champion of the tournament. A team is considered the champion if there is no other team that is stronger than it, meaning no edges are directed towards it. We want to return the index of that champion team. However, if there's no unique champion (either because there are multiple strongest teams or the graph structure doesn't allow for a single strongest team), we should return -1.

Intuition

The problem can be solved by analyzing the in-degree of each node (team) in the graph. The in-degree of a node is the number of edges directed towards it. If a team is the strongest, it means no other team can beat it, which implies that it should have an in-degree of 0—no edges pointing to it. Therefore:

1. We first initialize an array indeg to keep track of in-degrees for all nodes, with the size equal to the number of teams n.
2. We iterate over the edges array. For each directed edge [u, v], we increment the in-degree count for team v since the edge indicates that team u (index u) is stronger than team v (index v).
3. After populating the indeg array, we check for the following scenario:
   • If there is exactly one team with an in-degree of 0, that team is the champion as it is not outmatched by any other team.
   • If there is more than one team or no teams with an in-degree of 0, it means there is no unique champion, and we return -1.

The solution approach is straightforward and efficient because it relies on counting and analyzing in-degrees, which can be done in linear time with respect to the number of edges in the graph.

Learn more about Graph patterns.

Solution Approach

To implement our solution, we utilize a simple yet effective approach that revolves around the concept of in-degrees for nodes in a Directed Acyclic Graph (DAG). Our algorithm follows these steps:

1. We first create an array indeg which has the same length as the number of teams n. This array is used to keep track of the in-degrees for each node (team), and it is initialized with zeros since initially, we assume that no edges are directed towards any of the nodes.

2. We then iterate through the provided list of edges. For each edge [u, v] in the edges array, we know that the edge represents a match where team u is stronger than team v. Therefore, we increment the in-degree count of node v by 1, as this indicates another team is stronger than team v.

3. After processing all edges, we check the indeg array for the champion team. In a DAG, a node with an in-degree of 0 means there are no incoming edges, therefore no team is stronger than it. The champion team is then the unique node with an in-degree of 0.

4. The final step is to return the correct index. If there is exactly one team with an in-degree of 0, we return the index of this team, as it represents the champion. If there are multiple teams with an in-degree of 0 or if every team has an in-degree greater than 0, we return -1 to indicate there is no unique champion.

The solution uses a counting array to keep track of in-degrees, which is a common pattern when working with graph data structures that can easily represent dependencies or hierarchies.

The provided reference solution implements this strategy concisely in Python:

1class Solution:
2    def findChampion(self, n: int, edges: List[List[int]]) -> int:
3        indeg = [0] * n
4        for _, v in edges:
5            indeg[v] += 1
6        return -1 if indeg.count(0) != 1 else indeg.index(0)

In this implementation:

• indeg = [0] * n initializes the in-degree count array.
• The for _, v in edges: loop goes through the edges list and increments the in-degree count for the end node of every edge. The underscore _ is used to ignore the first element u of each edge since we only care about the in-degrees in this context.
• The final line uses a conditional expression to check the indeg array: indeg.count(0) != 1 checks if there's precisely one team with an in-degree of 0, and indeg.index(0) finds the index of that team. If the count is not 1, we return -1.

The algorithm's time complexity is O(m + n), where m is the number of edges, because we need to process each edge once, and n is the number of teams, as we need to check each team's in-degree and also return the index of the champion.

Example Walkthrough

Let's consider a simple example where we have n = 4 teams and the following set of edges that represent the outcome of the matches:

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

Using these edges, let's walk through the solution:

Step 1: We create an array indeg with size n and initialize it with zeros.

1indeg = [0, 0, 0, 0]

Each index corresponds to a team (0 through 3), and the value at that index will represent the team's in-degree.

Step 2: We iterate through the edges:

• For the first edge [0, 1], we increment the in-degree of team 1.

1indeg = [0, 1, 0, 0]

• For the second edge [2, 3], we increment the in-degree of team 3.

1indeg = [0, 1, 0, 1]

• For the third edge [2, 1], we increment the in-degree of team 1 again.

1indeg = [0, 2, 0, 1]

After processing all edges, the indeg array is [0, 2, 0, 1].

Step 3: We check for a unique team with an in-degree of 0. In our example, we have two teams (team 0 and team 2) with an in-degree of 0.

Step 4: We analyze the result. Since there are two teams with no incoming edges, there is no unique champion team. Therefore, according to the rules, we should return -1.

Using the provided Python implementation:

1class Solution:
2    def findChampion(self, n: int, edges: List[List[int]]) -> int:
3        indeg = [0] * n
4        for _, v in edges:
5            indeg[v] += 1
6        return -1 if indeg.count(0) != 1 else indeg.index(0)

If we call findChampion(4, [[0, 1], [2, 3], [2, 1]]), it will initialize the indeg array, increment the in-degrees accordingly, and then return -1 as there are multiple teams with an in-degree of 0.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n) where n is the number of nodes. This time complexity comes from having to iterate through all the edges once to calculate the in-degrees and then through all the nodes to find the one with an in-degree of 0.

The space complexity is also O(n), originating from the storage requirements of the indeg list that has to store an in-degree value for each of the n nodes.

Learn more about how to find time and space complexity quickly using problem constraints.