Course Schedule
Course Schedule is a medium graphs problem solved with the topological sort pattern.
The best approach, kahn's algorithm, runs in O(V + E) time and O(V + E) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from dfs cycle detection up.
Problem
There are numCourses courses. Each pair [a, b] in prerequisites means you must take course b before course a. Decide whether it is possible to finish every course.
Examples
Example 1
- Input
numCourses = 3, prerequisites = [[1,0],[2,1]]- Output
true- Why
- Take 0, then 1, then 2.
Example 2
- Input
numCourses = 2, prerequisites = [[1,0],[0,1]]- Output
false
Constraints
1 <= numCourses <= 2000; [a, b] means b must be taken before a.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| DFS cycle detection | O(V + E) | O(V + E) |
| Kahn's algorithm | O(V + E) | O(V + E) |
1DFS cycle detection
O(V + E)O(V + E)Build edges b → a and look for a back edge with three-state DFS.
- state 0/1/2; an edge into a state-1 node means a cycle, so return false.
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) adj.get(p[1]).add(p[0]);
int[] state = new int[numCourses];
for (int i = 0; i < numCourses; i++) if (state[i] == 0 && cyclic(i, adj, state)) return false;
return true;
}
private boolean cyclic(int u, List<List<Integer>> adj, int[] state) {
state[u] = 1;
for (int v : adj.get(u)) {
if (state[v] == 1) return true;
if (state[v] == 0 && cyclic(v, adj, state)) return true;
}
state[u] = 2;
return false;
}
}class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
adj = [[] for _ in range(numCourses)]
for p in prerequisites:
adj[p[1]].append(p[0])
state = [0] * numCourses
for i in range(numCourses):
if state[i] == 0 and self.cyclic(i, adj, state):
return False
return True
def cyclic(self, u: int, adj: List[List[int]], state: List[int]) -> bool:
state[u] = 1
for v in adj[u]:
if state[v] == 1:
return True
if state[v] == 0 and self.cyclic(v, adj, state):
return True
state[u] = 2
return Falseclass Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
for (auto& p : prerequisites) adj[p[1]].push_back(p[0]);
vector<int> state(numCourses, 0);
for (int i = 0; i < numCourses; i++) if (state[i] == 0 && cyclic(i, adj, state)) return false;
return true;
}
private:
bool cyclic(int u, vector<vector<int>>& adj, vector<int>& state) {
state[u] = 1;
for (int v : adj[u]) {
if (state[v] == 1) return true;
if (state[v] == 0 && cyclic(v, adj, state)) return true;
}
state[u] = 2;
return false;
}
};function canFinish(numCourses, prerequisites) {
const adj = Array.from({ length: numCourses }, () => []);
for (const p of prerequisites) adj[p[1]].push(p[0]);
const state = new Array(numCourses).fill(0);
function cyclic(u) {
state[u] = 1;
for (const v of adj[u]) {
if (state[v] === 1) return true;
if (state[v] === 0 && cyclic(v)) return true;
}
state[u] = 2;
return false;
}
for (let i = 0; i < numCourses; i++) if (state[i] === 0 && cyclic(i)) return false;
return true;
}2Kahn's algorithm
O(V + E)O(V + E)Take courses with no remaining prerequisites first. Each course taken lowers its dependants' in-degree. If every course gets taken, there is no cycle.
- indeg from edges b → a; queue zeros.
- Pop, taken++, decrement neighbours.
- Return taken == numCourses.
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
int[] indeg = new int[numCourses];
for (int[] p : prerequisites) { adj.get(p[1]).add(p[0]); indeg[p[0]]++; }
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.add(i);
int taken = 0;
while (!q.isEmpty()) {
int u = q.poll();
taken++;
for (int v : adj.get(u)) if (--indeg[v] == 0) q.add(v);
}
return taken == numCourses;
}
}class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
adj = [[] for _ in range(numCourses)]
indeg = [0] * numCourses
for p in prerequisites:
adj[p[1]].append(p[0])
indeg[p[0]] += 1
q = deque(i for i in range(numCourses) if indeg[i] == 0)
taken = 0
while q:
u = q.popleft()
taken += 1
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return taken == numCoursesclass Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
vector<int> indeg(numCourses, 0);
for (auto& p : prerequisites) { adj[p[1]].push_back(p[0]); indeg[p[0]]++; }
queue<int> q;
for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) q.push(i);
int taken = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
taken++;
for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
}
return taken == numCourses;
}
};function canFinish(numCourses, prerequisites) {
const adj = Array.from({ length: numCourses }, () => []);
const indeg = new Array(numCourses).fill(0);
for (const p of prerequisites) { adj[p[1]].push(p[0]); indeg[p[0]]++; }
const q = [];
for (let i = 0; i < numCourses; i++) if (indeg[i] === 0) q.push(i);
let taken = 0;
let head = 0;
while (head < q.length) {
const u = q[head++];
taken++;
for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
}
return taken === numCourses;
}Edge cases to test
- No prerequisites
- A course that requires itself
Hints
Hint 1
You can finish every course exactly when the prerequisite graph has no cycle.
FAQ
What is the best time complexity for Course Schedule?
Kahn's algorithm runs in O(V + E) time and O(V + E) extra space.
Which pattern does Course Schedule use?
It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Topological sort using BFS, Course Schedule II, Alien Dictionary.
Is there a brute force solution for Course Schedule?
Yes. DFS cycle detection takes O(V + E) time and O(V + E) space. Build edges b → a and look for a back edge with three-state DFS.
Which edge cases should I test for Course Schedule?
No prerequisites; A course that requires itself.