Course Schedule
Description
You are given a total of numCourses courses, labeled from 0 to numCourses - 1. You are also given an array prerequisites where prerequisites[i] = [a, b] means you must complete course b before you can take course a.
For example, the pair [0, 1] means to take course 0, you must first finish course 1.
Your task is to determine whether it is possible to finish all the courses. Return true if you can complete every course, or false if some courses create a circular dependency that makes completion impossible.
This problem is fundamentally about detecting whether a directed graph contains a cycle. Each course is a node, and each prerequisite [a, b] is a directed edge from b to a (meaning b must come before a). If there is a cycle in this graph, it means a set of courses mutually depend on each other, making it impossible to finish any of them.
Examples
Example 1
Input: numCourses = 2, prerequisites = [[1, 0]]
Output: true
Explanation: There are 2 courses (0 and 1). To take course 1, you must first finish course 0. There is no circular dependency — you can take course 0 first, then course 1. So it is possible to finish all courses.
Example 2
Input: numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
Explanation: There are 2 courses (0 and 1). To take course 1, you need course 0 first. But to take course 0, you need course 1 first. This creates a circular dependency (a cycle: 0 → 1 → 0), making it impossible to finish either course.
Example 3
Input: numCourses = 4, prerequisites = [[1, 0], [2, 1], [3, 2]]
Output: true
Explanation: The dependency chain is 0 → 1 → 2 → 3 (take 0 first, then 1, then 2, then 3). No cycles exist, so all courses can be completed in that order.
Constraints
- 1 ≤ numCourses ≤ 2000
- 0 ≤ prerequisites.length ≤ 5000
- prerequisites[i].length == 2
- 0 ≤ a_i, b_i < numCourses
- All the pairs prerequisites[i] are unique
Editorial
Brute Force
Intuition
The most straightforward way to check if all courses can be finished is to simulate the process. We repeatedly look for a course that has no remaining prerequisites (no unfinished dependencies). If we find one, we "take" it — remove it from the system and remove it as a prerequisite from all other courses. We keep doing this until either all courses are taken (return true) or we get stuck with no course having zero prerequisites (return false — a cycle exists).
Think of it like a to-do list where some tasks depend on others. You scan the list for anything you can do right now (no blockers). You do that task and cross it off. Then you scan again. If at some point nothing on the list can be done but tasks remain, you're stuck in a deadlock.
This simulation-based approach is essentially a naive version of topological sorting — but implemented inefficiently. Each "round" we scan all courses to find one with zero prerequisites, and after removing it, we update the prerequisite counts. This scanning is repeated up to n times (once per course), and each scan checks all edges.
Step-by-Step Explanation
Let's trace through with numCourses = 4, prerequisites = [[1,0], [2,0], [3,1], [3,2]]:
The graph: 0 → 1, 0 → 2, 1 → 3, 2 → 3.
In-degree counts: course 0 has 0 prerequisites, course 1 has 1 (needs 0), course 2 has 1 (needs 0), course 3 has 2 (needs 1 and 2).
Step 1: Scan all courses for one with 0 prerequisites. Course 0 has 0 prerequisites. Take course 0. Mark it as completed. Decrement prerequisite count for courses that depend on 0: course 1 (1→0), course 2 (1→0). Courses taken: 1.
Step 2: Scan again. Course 1 now has 0 prerequisites. Take course 1. Decrement prerequisite count for course 3 (2→1). Courses taken: 2.
Step 3: Scan again. Course 2 has 0 prerequisites. Take course 2. Decrement prerequisite count for course 3 (1→0). Courses taken: 3.
Step 4: Scan again. Course 3 now has 0 prerequisites. Take course 3. Courses taken: 4.
Result: All 4 courses taken. Return true. Each round required scanning all remaining courses — up to 4 scans per round, 4 rounds total.
Brute Force — Repeated Scanning for Zero-Prerequisite Courses — Watch how each round scans all courses to find one with zero prerequisites, takes it, and updates dependencies. The repeated scanning is the source of inefficiency.
Algorithm
- Build an adjacency list and compute in-degree for each course
- Repeat up to
numCoursestimes:
a. Scan all courses to find one with in-degree 0 that hasn't been taken
b. If no such course exists, return false (cycle detected)
c. Mark it as taken
d. Decrement in-degree of all courses it points to - If all courses are taken, return true
Code
#include <vector>
using namespace std;
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
vector<int> inDegree(numCourses, 0);
for (auto& p : prerequisites) {
adj[p[1]].push_back(p[0]);
inDegree[p[0]]++;
}
int taken = 0;
vector<bool> completed(numCourses, false);
for (int round = 0; round < numCourses; round++) {
// Scan for a course with in-degree 0
int found = -1;
for (int i = 0; i < numCourses; i++) {
if (!completed[i] && inDegree[i] == 0) {
found = i;
break;
}
}
if (found == -1) return false; // cycle
completed[found] = true;
taken++;
for (int neighbor : adj[found]) {
inDegree[neighbor]--;
}
}
return taken == numCourses;
}
};from typing import List
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
adj = [[] for _ in range(numCourses)]
in_degree = [0] * numCourses
for a, b in prerequisites:
adj[b].append(a)
in_degree[a] += 1
completed = [False] * numCourses
taken = 0
for _ in range(numCourses):
# Scan for course with in-degree 0
found = -1
for i in range(numCourses):
if not completed[i] and in_degree[i] == 0:
found = i
break
if found == -1:
return False # cycle
completed[found] = True
taken += 1
for neighbor in adj[found]:
in_degree[neighbor] -= 1
return taken == numCoursesimport java.util.*;
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) {
adj.get(p[1]).add(p[0]);
inDegree[p[0]]++;
}
boolean[] completed = new boolean[numCourses];
int taken = 0;
for (int round = 0; round < numCourses; round++) {
int found = -1;
for (int i = 0; i < numCourses; i++) {
if (!completed[i] && inDegree[i] == 0) {
found = i;
break;
}
}
if (found == -1) return false;
completed[found] = true;
taken++;
for (int neighbor : adj.get(found)) {
inDegree[neighbor]--;
}
}
return taken == numCourses;
}
}Complexity Analysis
Time Complexity: O(V² + V·E)
We run V rounds. In each round, we scan up to V courses to find one with in-degree 0 (O(V) per round), giving O(V²) for the scanning. Additionally, when we take a course, we update its neighbors — across all rounds, total edge updates are O(E). Combined: O(V² + E), which simplifies to O(V²) since E ≤ 5000 and V ≤ 2000.
Space Complexity: O(V + E)
We store the adjacency list (O(V + E)), in-degree array (O(V)), and completed array (O(V)). Total: O(V + E).
Why This Approach Is Not Efficient
The brute force works correctly but wastes time by scanning all courses every round to find one with in-degree 0. With V up to 2000, that's up to 4 million scanning operations — functional but unnecessary.
The core inefficiency: when we decrement a course's in-degree to 0, we already know it's eligible, but we don't act on that knowledge immediately. Instead, we wait until the next round and scan everything again to "discover" it.
The fix is simple: use a queue. Whenever a course's in-degree drops to 0, immediately add it to a queue. Then instead of scanning all courses each round, we just pop the next eligible course from the queue. This eliminates the O(V) scan per round, reducing total time from O(V²) to O(V + E).
This optimization transforms the naive simulation into Kahn's algorithm — the standard BFS-based topological sort.
Optimal Approach - BFS Topological Sort (Kahn's Algorithm)
Intuition
Kahn's algorithm is a Breadth-First Search (BFS) approach to topological sorting. It directly answers our question: can we order the courses such that every prerequisite comes before its dependent?
The key insight is the concept of in-degree — the number of prerequisites a course has. A course with in-degree 0 has no prerequisites and can be taken immediately.
The algorithm works like a cascading chain of dominoes:
- Find all courses with zero prerequisites (in-degree 0) and add them to a queue
- Process each course from the queue: take it, then reduce the in-degree of all courses that depend on it
- When a course's in-degree drops to 0, it means all its prerequisites have been completed — add it to the queue
- If we process all courses, there's no cycle. If the queue empties before all courses are processed, the remaining courses are trapped in a cycle.
Imagine a factory assembly line. Some tasks can start immediately (no dependencies). When a task finishes, it unlocks other tasks that were waiting for it. If every task eventually gets done, the line runs smoothly. If some tasks are deadlocked waiting for each other, production halts — that's a cycle.
Unlike the brute force that scans all courses each round, Kahn's algorithm only processes each course once (when it's dequeued) and each edge once (when decrementing in-degree). This gives O(V + E) time — optimal for graph traversal.
Step-by-Step Explanation
Let's trace through with numCourses = 4, prerequisites = [[1,0], [2,0], [3,1], [3,2]]:
Graph edges: 0→1, 0→2, 1→3, 2→3
Step 1: Compute in-degrees. Course 0: 0, course 1: 1, course 2: 1, course 3: 2. Initialize queue with all courses having in-degree 0: queue = [0].
Step 2: Dequeue course 0. Process it (taken = 1). Check neighbors: course 1 (in-degree 1→0, add to queue), course 2 (in-degree 1→0, add to queue). Queue = [1, 2].
Step 3: Dequeue course 1. Process it (taken = 2). Check neighbors: course 3 (in-degree 2→1). Course 3 still has unmet prereq. Queue = [2].
Step 4: Dequeue course 2. Process it (taken = 3). Check neighbors: course 3 (in-degree 1→0, add to queue). Queue = [3].
Step 5: Dequeue course 3. Process it (taken = 4). No neighbors. Queue = [].
Step 6: Queue empty. taken = 4 = numCourses. All courses completed. Return true.
BFS Topological Sort (Kahn's Algorithm) — Queue-Driven Course Processing — Watch how courses with zero in-degree are immediately queued and processed, cascading through the dependency graph without ever scanning all courses.
Algorithm
- Build an adjacency list from prerequisites: for each
[a, b], add edgeb → a - Compute in-degree for each course
- Initialize a queue with all courses having in-degree 0
- While the queue is not empty:
a. Dequeue a course, incrementtakencounter
b. For each neighbor of the dequeued course, decrement its in-degree
c. If a neighbor's in-degree becomes 0, enqueue it - Return
taken == numCourses
Code
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<vector<int>> adj(numCourses);
vector<int> inDegree(numCourses, 0);
for (auto& p : prerequisites) {
adj[p[1]].push_back(p[0]);
inDegree[p[0]]++;
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) q.push(i);
}
int taken = 0;
while (!q.empty()) {
int course = q.front();
q.pop();
taken++;
for (int neighbor : adj[course]) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
return taken == numCourses;
}
};from typing import List
from collections import deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
adj = [[] for _ in range(numCourses)]
in_degree = [0] * numCourses
for a, b in prerequisites:
adj[b].append(a)
in_degree[a] += 1
queue = deque()
for i in range(numCourses):
if in_degree[i] == 0:
queue.append(i)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for neighbor in adj[course]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return taken == numCoursesimport java.util.*;
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDegree = new int[numCourses];
for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
for (int[] p : prerequisites) {
adj.get(p[1]).add(p[0]);
inDegree[p[0]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) queue.offer(i);
}
int taken = 0;
while (!queue.isEmpty()) {
int course = queue.poll();
taken++;
for (int neighbor : adj.get(course)) {
inDegree[neighbor]--;
if (inDegree[neighbor] == 0) {
queue.offer(neighbor);
}
}
}
return taken == numCourses;
}
}Complexity Analysis
Time Complexity: O(V + E)
Where V = numCourses and E = number of prerequisites. We iterate through all edges once to build the graph and compute in-degrees (O(E)). Each course is enqueued and dequeued at most once (O(V)). Each edge is processed exactly once when decrementing in-degrees (O(E)). Total: O(V + E).
This is optimal — any solution must at minimum examine every course and every prerequisite edge.
Space Complexity: O(V + E)
The adjacency list stores all edges (O(V + E)). The in-degree array and queue both use O(V) space. Total: O(V + E).