In this guide, you will get 207. Course Schedule LeetCode Solution with the best time and space complexity. The solution to Course Schedule 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.
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 bi first if you want to take course ai.
For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.
Return true if you can finish all courses. Otherwise, return false.
Example 1:
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0. So it is possible.
Example 2:
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Constraints:
1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique.
Time Complexity: O(|V| + |E|), where |V| = \texttt{numCourses} and |E| = |\texttt{prerequisites}|
Space Complexity: O(|V| + |E|), where |V| = \texttt{numCourses} and |E| = |\texttt{prerequisites}|
207. Course Schedule LeetCode Solution in C++
enum class State { kInit, kVisiting, kVisited };
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> graph(numCourses);
vector<State> states(numCourses);
for (const vector<int>& prerequisite : prerequisites) {
const int u = prerequisite[1];
const int v = prerequisite[0];
graph[u].push_back(v);
}
for (int i = 0; i < numCourses; ++i)
if (hasCycle(graph, i, states))
return false;
return true;
}
private:
bool hasCycle(const vector<vector<int>>& graph, int u,
vector<State>& states) {
if (states[u] == State::kVisiting)
return true;
if (states[u] == State::kVisited)
return false;
states[u] = State::kVisiting;
for (const int v : graph[u])
if (hasCycle(graph, v, states))
return true;
states[u] = State::kVisited;
return false;
}
}; /* code provided by PROGIEZ */
207. Course Schedule LeetCode Solution in Java
enum State { kInit, kVisiting, kVisited }
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<Integer>[] graph = new List[numCourses];
State[] states = new State[numCourses];
for (int i = 0; i < numCourses; ++i)
graph[i] = new ArrayList<>();
for (int[] prerequisite : prerequisites) {
final int u = prerequisite[1];
final int v = prerequisite[0];
graph[u].add(v);
}
for (int i = 0; i < numCourses; ++i)
if (hasCycle(graph, i, states))
return false;
return true;
}
private boolean hasCycle(List<Integer>[] graph, int u, State[] states) {
if (states[u] == State.kVisiting)
return true;
if (states[u] == State.kVisited)
return false;
states[u] = State.kVisiting;
for (final int v : graph[u])
if (hasCycle(graph, v, states))
return true;
states[u] = State.kVisited;
return false;
}
} // code provided by PROGIEZ
207. Course Schedule LeetCode Solution in Python
from enum import Enum
class State(Enum):
kInit = 0
kVisiting = 1
kVisited = 2
class Solution:
def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
graph = [[] for _ in range(numCourses)]
states = [State.kInit] * numCourses
for v, u in prerequisites:
graph[u].append(v)
def hasCycle(u: int) -> bool:
if states[u] == State.kVisiting:
return True
if states[u] == State.kVisited:
return False
states[u] = State.kVisiting
if any(hasCycle(v) for v in graph[u]):
return True
states[u] = State.kVisited
return False
return not any(hasCycle(i) for i in range(numCourses)) # code by PROGIEZ
