Leetcode 2924: Find Champion II
In a tournament, there are ’n’ teams numbered from 0 to n-1, where each team is represented as a node in a Directed Acyclic Graph (DAG). You are given an integer ’n’ and a 2D integer array ’edges’, where each element edges[i] = [ui, vi] indicates a directed edge from team ‘ui’ to team ‘vi’, meaning team ‘ui’ is stronger than team ‘vi’. A team will be the champion of the tournament if no other team is stronger than it. If there is exactly one champion, return its index; otherwise, return -1.
Problem
Approach
Steps
Complexity
Input: You are given two inputs: an integer 'n' representing the number of teams, and a 2D integer array 'edges' where each element defines a directed edge between two teams.
Example: For n = 3 and edges = [[0, 1], [1, 2]], the result will be 0.
Constraints:
• 1 <= n <= 100
• m == edges.length
• 0 <= m <= n * (n - 1) / 2
• edges[i].length == 2
• 0 <= edge[i][j] <= n - 1
• edges[i][0] != edges[i][1]
• The input is generated such that there are no cycles in the graph.
Output: Return the index of the champion team if there is exactly one champion; otherwise, return -1.
Example: For n = 4 and edges = [[0, 2], [1, 3], [1, 2]], the output will be -1.
Constraints:
• The output will either be a valid team index or -1 if no unique champion exists.
Goal: The goal is to find the team that has no incoming edges, meaning no other team is stronger than it. If more than one team has no incoming edges, return -1.
Steps:
• Compute the indegree (number of incoming edges) for each team.
• Check how many teams have zero indegree.
• If exactly one team has zero indegree, that is the champion. Otherwise, return -1.
Goal: The graph is a Directed Acyclic Graph (DAG), meaning there are no cycles. The input size will be reasonable, with 'n' up to 100 teams.
Steps:
• The graph will be acyclic and the number of edges will not exceed n * (n - 1) / 2.
Assumptions:
• The input will be valid and follow the constraints specified.
• Input: Example 1: n = 3, edges = [[0, 1], [1, 2]]
• Explanation: In this case, team 0 is stronger than team 1, and team 1 is stronger than team 2. Therefore, team 0 is the champion because it has no incoming edges.
• Input: Example 2: n = 4, edges = [[0, 2], [1, 3], [1, 2]]
• Explanation: Here, both teams 0 and 1 have no incoming edges, meaning there is no unique champion. Therefore, the result is -1.
Approach: To solve this problem, we need to find the team that no other team is stronger than. We can do this by calculating the indegree of each team and determining if there is exactly one team with zero indegree.
Observations:
• The problem is based on identifying the root node(s) in a DAG, where the root node has no incoming edges.
• We need to keep track of the indegrees for each team and check if there is exactly one team with an indegree of zero.
Steps:
• Initialize an array to keep track of indegrees for each team.
• Iterate over the edges and update the indegree for the destination team of each edge.
• Count how many teams have an indegree of zero.
• If there is exactly one team with an indegree of zero, return its index. Otherwise, return -1.
Empty Inputs:
• The input will never be empty since there is always at least one team.
Large Inputs:
• The algorithm should efficiently handle the upper limit where n = 100.
Special Values:
• When n = 1, the only team will be the champion.
Constraints:
• The graph will always be acyclic, and no team will be stronger than itself.
int findChampion(int n, vector<vector<int>>& edges) {
int ans = -1, count = 0;
vector<int> indegree(n, 0);
for(auto e: edges) indegree[e[1]]++;
for(int i = 0; i < n; ++i) {
if(indegree[i] == 0) {count++; ans = i; }
}
return count > 1?-1:ans;
}
1 : Function Definition
int findChampion(int n, vector<vector<int>>& edges) {
Defines the 'findChampion' function, which takes the number of nodes 'n' and a list of directed edges 'edges' as input, returning the index of the champion or -1 if there is no unique champion.
2 : Variable Initialization
int ans = -1, count = 0;
Initializes variables: 'ans' to store the champion node (default is -1), and 'count' to track how many nodes have indegree 0.
3 : Indegree Array Setup
vector<int> indegree(n, 0);
Creates a vector 'indegree' of size 'n' to store the indegree of each node. Initially, all values are set to 0.
4 : Indegree Calculation
for(auto e: edges) indegree[e[1]]++;
Iterates over the list of directed edges, incrementing the indegree of the destination node 'e[1]' for each edge.
5 : Loop Over Nodes
for(int i = 0; i < n; ++i) {
Iterates over all nodes in the graph to check which node has indegree 0.
6 : Champion Detection
if(indegree[i] == 0) {count++; ans = i; }
If a node has indegree 0 (no incoming edges), it is a potential champion. The 'count' is incremented, and 'ans' is set to the current node index 'i'.
7 : Return Result
return count > 1?-1:ans;
Returns the champion node if exactly one node has indegree 0, otherwise returns -1 if there are multiple such nodes.
Best Case: O(n)
Average Case: O(m + n)
Worst Case: O(m + n)
Description: The time complexity depends on the number of teams (n) and edges (m). In the worst case, we iterate through all edges and teams.
Best Case: O(n)
Worst Case: O(n + m)
Description: We need space for the indegree array and the input edges.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus