Leetcode 1462. Course Schedule IV

Problem Explanation

You are given a total of n courses, labeled from 0 to n-1. Some of these courses may have prerequisites, meaning that before you can take course B, you must first complete course A. These prerequisites are given as a pair such as [A, B].

Your task is to determine if based on a given set of queries, whether a course i is the prerequisite of course j or not.

To clarify, if A is a prerequisite of B, and B is a prerequisite of C, then A is also a prerequisite of C.

You should return a list of boolean values indicating whether each of the queries in order correlates a course and its prerequisite.

For example, if n = 2 and the prerequisites are [[1,0]] and given queries are [[0,1],[1,0]], your function should return [false, true] because course 0 is not a prerequisite of course 1 but course 1 is a prerequisite of course 0.

Solution Approach

The task is actually an application of Depth-First Search on directed graphs. For every course, we can perform a DFS to mark out all courses that are reachable from it.

Firstly, from the prerequisites list, we will construct the graph, where graph[i] contains all courses that can be reached directly from course i.

Next, we launch separate DFS from every course and mark out all courses that are reachable from it in the isPrerequisite array.

Finally we can just check the query pair against the isPrerequisite array and append the result to our answer.

Therefore, the key data structures here are the adjacency list graph for identifying the neighboring courses in the directed graph and the isPrerequisite 2D array for storing the DFS traversal results.

For example, if n = 5 and the prerequisites are [[0, 1], [1, 2], [2, 3], [3, 4]] and given queries are [[0,4],[4,0],[1,3],[3,0]], the graph is represented as follows:

1
2
30 -> 1
41 -> 2
52 -> 3
63 -> 4

After performing DFS for each course, isPrerequisite are represented as follows:

1
2
30 -> [false, true, true, true, true]
41 -> [false, false, true, true, true]
52 -> [false, false, false, true, true]
63 -> [false, false, false, false, true]
74 -> [false, false, false, false, false]

Then, checking each query, for query [0,4], course 0 is a prerequisite of course 4, for query [4,0], course 4 is not a prerequisite of course 0, for query [1,3], course 1 is a prerequisite of course 3, for query [3,0], course 3 is not a prerequisite of course 0.

So, the output would be [true,false,true,false].

Solution Code

Python Solution

1
2python
3from collections import defaultdict
4
5class Solution:
6    def checkIfPrerequisite(self, numCourses: int, prerequisites: List[List[int]], queries: List[List[int]]) -> List[bool]:
7        graph = defaultdict(set)
8        for u, v in prerequisites:
9            graph[v].add(u)
10
11        isPrerequisite = defaultdict(set)
12        visited = [0] * numCourses
13
14        def dfs(u):
15            for v in graph[u]:
16                if v not in isPrerequisite[u]:
17                    isPrerequisite[u].add(v)
18                    dfs(v)
19                    isPrerequisite[u] |= isPrerequisite[v]
20
21        for u in list(graph):
22            if not visited[u]:
23                dfs(u)
24
25        return [u in isPrerequisite[v] for u, v in queries]

Java Solution

1
2java
3import java.util.ArrayList;
4import java.util.List;
5
6class Solution {
7    public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
8        List<List<Integer>> graph = new ArrayList<>();
9        for (int i = 0; i < numCourses; ++i)
10            graph.add(new ArrayList<>());
11        for (int[] p : prerequisites)
12            graph.get(p[0]).add(p[1]);
13        
14        boolean[][] connected = new boolean[numCourses][numCourses];
15        for (int i = 0; i < numCourses; ++i)
16            dfs(graph, i, i, connected);
17        
18        List<Boolean> ans = new ArrayList<>();
19        for (int[] query : queries)
20            ans.add(connected[query[0]][query[1]]);
21        
22        return ans;
23    }
24    
25    void dfs(List<List<Integer>> graph, int start, int cur, boolean[][] connected) {
26        connected[start][cur] = true;
27        for (int next : graph.get(cur)) {
28            if (!connected[start][next])
29                dfs(graph, start, next, connected);
30        }
31    }
32}

C++ Solution

1
2cpp
3class Solution {
4public:
5    vector<bool> checkIfPrerequisite(int numCourses, vector<vector<int>>& prerequisites, vector<vector<int>>& queries) {
6        vector<bool> ans;
7        vector<vector<int>> graph(numCourses);
8        // isPrerequisite[i][j] is true if course i is a prerequisite of course j.
9        vector<vector<bool>> isPrerequisite(numCourses, vector<bool>(numCourses));
10
11        for (const vector<int>& prerequisite : prerequisites) {
12            const int u = prerequisite[0];
13            const int v = prerequisite[1];
14            graph[u].push_back(v);
15        }
16
17        // DFS from every course.
18        for (int i = 0; i < numCourses; ++i)
19            dfs(graph, i, isPrerequisite[i]);
20
21        for (const vector<int>& query : queries) {
22            const int u = query[0];
23            const int v = query[1];
24            ans.push_back(isPrerequisite[u][v]);
25        }
26
27        return ans;
28    }
29
30    void dfs(const vector<vector<int>>& graph, int u, vector<bool>& used) {
31        for (const int v : graph[u]) {
32            if (used[v])
33                continue;
34            used[v] = true;
35            dfs(graph, v, used);
36        }
37    }
38};

C# Solution

1
2csharp
3public class Solution {
4    public IList<bool> CheckIfPrerequisite(int numC, int[][] pre, int[][] qs) {
5        var m = new bool[numC,numC];
6        foreach (var p in pre)
7            m[p[0], p[1]] = true;
8        
9        for (var k = 0; k < numC; ++k)
10            for (var i = 0; i < numC; ++i)
11                for (var j = 0; j < numC; ++j)
12                    m[i,j] = m[i,j] || m[i,k] && m[k,j];
13    
14        return qs.Select(q => m[q[0], q[1]]).ToList();
15    }
16}

JavaScript Solution

1
2javascript
3var checkIfPrerequisite = function(numC, pre, qs) {
4    var m = [...Array(numC)].map(x=>Array(numC).fill(false));
5    for (var p of pre)
6        m[p[0]][p[1]] = true;
7    
8    for (var k = 0; k < numC; ++k)
9        for (var i = 0; i < numC; ++i)
10            for (var j = 0; j < numC; ++j)
11                m[i][j] = m[i][j] || m[i][k] && m[k][j];
12    
13    return qs.map(q => m[q[0]][q[1]]);
14};

The solution presented for each of the languages applies the same approach using the language's specific syntax and standard library. As a reminder, this solution makes use of depth-first search and a 2D adjacency matrix. We pre-compute all possible course prerequisites using depth-first search. This will allow us to quickly check if a given course is a prerequisite for another course for each of the queries.

The time complexity of the solution is O(N^3), where N is the number of courses.This is due to the cubic loop structure when filling out our 2D isPrerequisite matrix. The space complexity is O(N^2), where N is the number of courses. This is the amount of space allocated for our 2D isPrerequisite matrix.

Therefore, this problem requires a firm understanding of depth-first search and graph representation. With these tools, we can leverage a pre-processing step to simplify the problem and allow for a straightforward verification of the queries.

Note also that the given solution assumes that the input prerequisites and queries are valid. In a real-world setting, it could be beneficial to add some error handling to ensure that the input satisfies all necessary constraints. For instance, you might want to check that all course numbers in the prerequisites and queries are in the range from 0 to n - 1.

Problem Extensions

The problem can also be extended in several interesting ways:

1. Multiple prerequisites: Suppose that a course could have multiple prerequisites. For example, Course B might require both Course A and Course C as prerequisites. The solution would need to be modified to handle these additional relationships.
2. Prerequisite chains: Suppose that there was a chain of prerequisites. For example, Course A is a prerequisite for Course B, which is a prerequisite for Course C, and so on. The solution would need to consider all these chains as well.
3. Bi-directional prerequisites: Suppose that two courses could be prerequisites for each other. For example, Course A is a prerequisite for Course B and Course B is also a prerequisite for Course A. The solution must consider these cycles and possibly identify them as invalid.

These are just a few of many possible interpretations and extensions of this problem. This just goes to show you the depth and breadth of possibility when it comes to problem-solving with algorithms and data structures. Understanding the core principles behind each approach can open up a world of potential solutions to even the most complex problems.