1462. Course Schedule IV LeetCode Solution
In this guide, you will get 1462. Course Schedule IV LeetCode Solution with the best time and space complexity. The solution to Course Schedule IV problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Course Schedule IV solution in C++
- Course Schedule IV solution in Java
- Course Schedule IV solution in Python
- Additional Resources
Problem Statement of Course Schedule IV
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 course 0 before you can take course 1.
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
Complexity Analysis
- Time Complexity: O(n^3)
- Space Complexity: O(n^2)
1462. Course Schedule IV LeetCode Solution in C++
class Solution {
public:
vector<bool> checkIfPrerequisite(int numCourses,
vector<vector<int>>& prerequisites,
vector<vector<int>>& queries) {
vector<bool> ans;
vector<vector<int>> graph(numCourses);
// isPrerequisite[i][j] := true if course i is a prerequisite of course j
vector<vector<bool>> isPrerequisite(numCourses, vector<bool>(numCourses));
for (const vector<int>& prerequisite : prerequisites) {
const int u = prerequisite[0];
const int v = prerequisite[1];
graph[u].push_back(v);
}
// DFS from every course.
for (int i = 0; i < numCourses; ++i)
dfs(graph, i, isPrerequisite[i]);
for (const vector<int>& query : queries) {
const int u = query[0];
const int v = query[1];
ans.push_back(isPrerequisite[u][v]);
}
return ans;
}
void dfs(const vector<vector<int>>& graph, int u, vector<bool>& used) {
for (const int v : graph[u]) {
if (used[v])
continue;
used[v] = true;
dfs(graph, v, used);
}
}
};
/* code provided by PROGIEZ */1462. Course Schedule IV LeetCode Solution in Java
class Solution {
public boolean[] checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
List<Boolean> ans = new ArrayList<>();
List<Integer>[] graph = new List[numCourses];
// isPrerequisite[i][j] := true if course i is a prerequisite of course j
boolean[][] isPrerequisite = new boolean[numCourses][numCourses];
for (int i = 0; i < numCourses; ++i)
graph[i] = new ArrayList<>();
for (int[] prerequisite : prerequisites) {
final int u = prerequisite[0];
final int v = prerequisite[1];
graph[u].add(v);
}
// DFS from every course.
for (int i = 0; i < numCourses; ++i)
dfs(graph, i, isPrerequisite[i]);
for (int[] query : queries) {
final int u = query[0];
final int v = query[1];
ans.add(isPrerequisite[u][v]);
}
return ans;
}
public void dfs(const vector<vector<int>> &graph, int u, boolean[] used) {
for (final int v : graph[u]) {
if (used[v])
continue;
used[v] = true;
dfs(graph, v, used);
}
}
}
class Solution {
public List<Boolean> checkIfPrerequisite(int numCourses, int[][] prerequisites, int[][] queries) {
List<Boolean> ans = new ArrayList<>();
List<Integer>[] graph = new List[numCourses];
for (int i = 0; i < numCourses; ++i)
graph[i] = new ArrayList<>();
for (int[] prerequisite : prerequisites) {
final int u = prerequisite[0];
final int v = prerequisite[1];
graph[u].add(v);
}
// isPrerequisite[i][j] := true if course i is a prerequisite of course j
boolean[][] isPrerequisite = new boolean[numCourses][numCourses];
// DFS from every course.
for (int i = 0; i < numCourses; ++i)
dfs(graph, i, isPrerequisite[i]);
for (int[] query : queries) {
final int u = query[0];
final int v = query[1];
ans.add(isPrerequisite[u][v]);
}
return ans;
}
public void dfs(List<Integer>[] graph, int u, boolean[] used) {
for (final int v : graph[u]) {
if (used[v])
continue;
used[v] = true;
dfs(graph, v, used);
}
}
}
// code provided by PROGIEZ1462. Course Schedule IV LeetCode Solution in Python
class Solution:
def checkIfPrerequisite(
self,
numCourses: int,
prerequisites: list[list[int]],
queries: list[list[int]],
) -> list[bool]:
graph = [[] for _ in range(numCourses)]
# isPrerequisite[i][j] := True if course i is a prerequisite of course j.
isPrerequisite = [[False] * numCourses for _ in range(numCourses)]
for u, v in prerequisites:
graph[u].append(v)
# DFS from every course.
for i in range(numCourses):
self._dfs(graph, i, isPrerequisite[i])
return [isPrerequisite[u][v] for u, v in queries]
def _dfs(self, graph: list[list[int]], u: int, used: list[bool]) -> None:
for v in graph[u]:
if used[v]:
continue
used[v] = True
self._dfs(graph, v, used)
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.