1462. Course Schedule IV
Difficulty: Medium
Topics: Depth-First Search
, Breadth-First Search
, Graph
, Topological Sort
There are a total of numCourses
courses you have to take, labeled from 0
to numCourses - 1
. You are given an array prerequisites
where prerequisites[i] = [ai, bi]
indicates that you must take course ai
first if you want to take course bi
.
- For example, the pair
[0, 1]
indicates that you have to take course0
before you can take course1
.
Prerequisites can also be indirect. If course a
is a prerequisite of course b
, and course b
is a prerequisite of course c
, then course a
is a prerequisite of course c
.
You are also given an array queries
where queries[j] = [uj, vj]
. For the jth
query, you should answer whether course uj
is a prerequisite of course vj
or not.
Return a boolean array answer
, where answer[j]
is the answer to the jth
query.
Example 1:
- Input: numCourses = 2, prerequisites = [[1,0]], queries = [[0,1],[1,0]]
- Output: [false,true]
- Explanation: The pair [1, 0] indicates that you have to take course 1 before you can take course 0. Course 0 is not a prerequisite of course 1, but the opposite is true.
Example 2:
- Input: numCourses = 2, prerequisites = [], queries = [[1,0],[0,1]]
- Output: [false,false]
- Explanation: There are no prerequisites, and each course is independent.
Example 3:
- Input: numCourses = 3, prerequisites = [[1,2],[1,0],[2,0]], queries = [[1,0],[1,2]]
- Output: [true,true]
Constraints:
2 <= numCourses <= 100
0 <= prerequisites.length <= (numCourses * (numCourses - 1) / 2)
prerequisites[i].length == 2
0 <= ai, bi <= numCourses - 1
ai != bi
- All the pairs
[ai, bi]
are unique. - The prerequisites graph has no cycles.
1 <= queries.length <= 104
0 <= ui, vi <= numCourses - 1
ui != vi
Hint:
- Imagine if the courses are nodes of a graph. We need to build an array isReachable[i][j].
- Start a bfs from each course i and assign for each course j you visit isReachable[i][j] = True.
- Answer the queries from the isReachable array.
Solution:
We can use a graph representation and the Floyd-Warshall algorithm to compute whether each course is reachable from another course. This approach will efficiently handle the prerequisite relationships and allow us to answer the queries directly.
Let's implement this solution in PHP: 1462. Course Schedule IV
<?php
/**
* @param Integer $numCourses
* @param Integer[][] $prerequisites
* @param Integer[][] $queries
* @return Boolean[]
*/
function checkIfPrerequisite($numCourses, $prerequisites, $queries) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example usage:
$numCourses = 2;
$prerequisites = [[1,0]];
$queries = [[0,1],[1,0]];
$result = checkIfPrerequisite($numCourses, $prerequisites, $queries);
print_r($result); // Output: [false,true]
$numCourses = 2;
$prerequisites = [];
$queries = [[1,0],[0,1]]
$result = checkIfPrerequisite($numCourses, $prerequisites, $queries);
print_r($result); // Output: [false,false]
$numCourses = 3;
$prerequisites = [[1, 2], [1, 0], [2, 0]];
$queries = [[1, 0], [1, 2]];
$result = checkIfPrerequisite($numCourses, $prerequisites, $queries);
print_r($result); // Output: [true, true]
?>
Explanation:
-
Graph Initialization:
- The
$isReachable
2D array is initialized tofalse
, representing that no course is reachable from another initially.
- The
-
Direct Prerequisites:
- We populate the
$isReachable
array based on theprerequisites
. For every prerequisite[a, b]
, coursea
must be taken before courseb
.
- We populate the
-
Floyd-Warshall Algorithm:
- This algorithm calculates the transitive closure of the graph.
- For every intermediate course
k
, we check if coursei
is reachable from coursej
throughk
. If yes, we mark$isReachable[i][j] = true
.
-
Query Evaluation:
- Each query
[u, v]
is answered by simply checking the value of$isReachable[u][v]
.
- Each query
Complexity:
-
Time Complexity:
- Floyd-Warshall algorithm: O(numCourses3)
- Queries: O(queries.length)
- Total: O(numCourses3 + queries.length)
-
Space Complexity:
- The space used by the
$isReachable
array is O(numCourses2).
- The space used by the
Example Walkthrough:
Input:
$numCourses = 3;
$prerequisites = [[1, 2], [1, 0], [2, 0]];
$queries = [[1, 0], [1, 2]];
Execution:
- After initializing the graph:
$isReachable = [
[false, false, false],
[false, false, true],
[false, false, false]
];
- After Floyd-Warshall:
$isReachable = [
[false, false, false],
[true, false, true],
[true, false, false]
];
- Answering queries:
- Query
[1, 0]
:true
- Query
[1, 2]
:true
- Query
Output:
[true, true]
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)