Course Schedule
Understand the problem
There are numCourses courses (numbered 0 to numCourses-1). The prerequisites array holds pairs [a, b], meaning you must take b before a. Can you finish all the courses?
Example:
ts
numCourses = 2, prerequisites = [[1,0]]
output = true // take 0 first, then 1
numCourses = 2, prerequisites = [[1,0],[0,1]]
output = false // 0 needs 1, 1 needs 0 — a cycle!The problem reduces to: does the directed graph prerequisites contain a cycle? If it does → you can't finish.
If not → a valid topological order exists.
Basic approach
O(V + E) time, O(V + E) spacets
// Kahn's BFS (Topological Sort) — more intuitive with in-degree
function canFinishBFS(numCourses: number, prerequisites: number[][]): boolean {
const inDegree = new Array(numCourses).fill(0)
const adj: number[][] = Array.from({ length: numCourses }, () => [])
for (const [a, b] of prerequisites) {
adj[b].push(a)
inDegree[a]++
}
const queue: number[] = []
for (let i = 0; i < numCourses; i++) {
if (inDegree[i] === 0) queue.push(i)
}
let processed = 0
while (queue.length > 0) {
const node = queue.shift()!
processed++
for (const next of adj[node]) {
inDegree[next]--
if (inDegree[next] === 0) queue.push(next)
}
}
return processed === numCourses
}Why this approach is slow:
Kahn's BFS uses in-degree to detect cycles: if, after processing every node with in-degree=0, some nodes are still unprocessed → there's a cycle.
- This is an acceptable brute-force approach, but DFS with 3-color states is asked more often.
- Note that the in-degree array is initialized to 0 for every node.
Unlock the optimal solution, the step-by-step trace and related questions
See the full step-by-step trace, Big-O and edge cases.