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:
- We first initialize an array
indeg
to keep track of in-degrees for all nodes, with the size equal to the number of teamsn
. - We iterate over the
edges
array. For each directed edge[u, v]
, we increment the in-degree count for teamv
since the edge indicates that teamu
(indexu
) is stronger than teamv
(indexv
). - 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
.
- If there is exactly one team with an in-degree of
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:
-
We first create an array
indeg
which has the same length as the number of teamsn
. 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. -
We then iterate through the provided list of edges. For each edge
[u, v]
in theedges
array, we know that the edge represents a match where teamu
is stronger than teamv
. Therefore, we increment the in-degree count of nodev
by 1, as this indicates another team is stronger than teamv
. -
After processing all edges, we check the
indeg
array for the champion team. In a DAG, a node with an in-degree of0
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 of0
. -
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 of0
or if every team has an in-degree greater than0
, 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:
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)
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 elementu
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 of0
, andindeg.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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
edges = [[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.
indeg = [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.
indeg = [0, 1, 0, 0]
- For the second edge
[2, 3]
, we increment the in-degree of team 3.
indeg = [0, 1, 0, 1]
- For the third edge
[2, 1]
, we increment the in-degree of team 1 again.
indeg = [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:
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)
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
1from typing import List
2
3class Solution:
4 def findChampion(self, n: int, edges: List[List[int]]) -> int:
5 # Create a list to keep track of in-degrees for all the nodes
6 in_degree = [0] * n
7
8 # Iterate over each edge in the graph
9 for _, destination in edges:
10 # Increment the in-degree for the destination node of each edge
11 in_degree[destination] += 1
12
13 # Find if there is exactly one node with an in-degree of 0
14 # This node is the potential champion as it has no incoming edges
15 if in_degree.count(0) == 1:
16 # Return the index of the node with an in-degree of 0
17 return in_degree.index(0)
18 else:
19 # If there is not exactly one node with in-degree 0, return -1
20 return -1
21
1class Solution {
2 // Method to find the "champion" node.
3 // The champion is defined as the unique node with no incoming edges.
4 public int findChampion(int n, int[][] edges) {
5 // Array to store the incoming degree count for each node
6 int[] incomingDegreeCounts = new int[n];
7
8 // Loop through all edges to calculate the incoming degree counts
9 for (int[] edge : edges) {
10 // Increment the count of incoming edges for the destination node
11 incomingDegreeCounts[edge[1]]++;
12 }
13
14 // Variable to store the champion node index, initialized as -1 (not found)
15 int champion = -1;
16 // Counter to keep track of how many nodes have zero incoming edges
17 int zeroIncomingCount = 0;
18
19 // Loop through all nodes to find the champion node
20 for (int i = 0; i < n; ++i) {
21 // Check if the current node has zero incoming edges
22 if (incomingDegreeCounts[i] == 0) {
23 // Increment the counter for nodes with zero incoming edges
24 zeroIncomingCount++;
25 // Set the current node as the potential champion
26 champion = i;
27 }
28 }
29
30 // Check if there is exactly one node with zero incoming edges
31 // If so, return the index of the champion node; otherwise, return -1
32 return zeroIncomingCount == 1 ? champion : -1;
33 }
34}
35
1class Solution {
2public:
3 int findChampion(int n, vector<vector<int>>& edges) {
4 // Create an array to track the in-degree (number of incoming edges) of each node
5 int inDegree[n];
6 memset(inDegree, 0, sizeof(inDegree)); // Initialize all in-degree values to 0
7
8 // Iterate through the edges and increment the in-degree of the destination nodes
9 for (auto& edge : edges) {
10 ++inDegree[edge[1]];
11 }
12
13 int champion = -1; // Variable to store the candidate node for champion
14 int zeroInDegreeCount = 0; // Counter to keep track of the number of nodes with 0 in-degrees
15
16 // Iterate through all nodes to find the node with 0 in-degree, if any
17 for (int i = 0; i < n; ++i) {
18 if (inDegree[i] == 0) { // A node with 0 in-degree can be a candidate for champion
19 ++zeroInDegreeCount;
20 champion = i; // Update candidate node
21 }
22 }
23
24 // If there is exactly one node with 0 in-degree, it is the champion
25 // Otherwise, there is no champion (return -1)
26 return zeroInDegreeCount == 1 ? champion : -1;
27 }
28};
29
1// Function to find the "champion" node in a directed graph.
2// The champion node is one that has no incoming edges.
3// Only one such node must exist for it to be the champion.
4// If more than one such node exists or if none exists, return -1.
5function findChampion(n: number, edges: number[][]): number {
6 // Initialize an array to track the number of incoming edges (indegree) for each node.
7 const indegrees: number[] = Array(n).fill(0);
8
9 // Populate the indegrees array by incrementing the indegree for every destination node
10 // in the edges.
11 for (const [, destination] of edges) {
12 ++indegrees[destination];
13 }
14
15 // Initialize variables to store the answer (the championās index) and a count of nodes with 0 indegree.
16 let answer: number = -1;
17 let zeroIndegreeCount: number = 0;
18
19 // Iterate over each node and find nodes with an indegree of 0 (no incoming edges).
20 for (let i = 0; i < n; ++i) {
21 if (indegrees[i] === 0) {
22 // If a node with no incoming edges is found, increment the count and update the answer.
23 ++zeroIndegreeCount;
24 answer = i;
25 }
26 }
27
28 // If there is exactly one node with no incoming edges, return that node's index.
29 // Otherwise, return -1 to indicate that no champion was found.
30 return zeroIndegreeCount === 1 ? answer : -1;
31}
32
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.
Depth first search is equivalent to which of the tree traversal order?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!