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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

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

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.


Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄