Course Schedule

Explanation & Solution

Description

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.

Input: numCourses = 2, prerequisites = [[1,0]]

Output: true

Explanation: There are 2 courses to take. To take course 1 you must first take course 0. This is possible.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
All the pairs prerequisites[i] are unique

Approach

Topological Sort pattern

1. Build the Adjacency List and In-Degree Array

Create a directed graph where an edge from prereq to course means prereq must come before course
Track the in-degree (number of prerequisites) for each course

2. Initialize the Queue with Zero In-Degree Nodes

Find all courses with no prerequisites (inDegree[i] === 0)
These courses can be taken immediately — add them to the BFS queue

3. Process Courses Using BFS (Kahn's Algorithm)

Dequeue a course and increment the processed count
For each course that depends on it, decrement its in-degree
If a neighbor's in-degree drops to 0, it has no remaining prerequisites — enqueue it

4. Check for Cycles

If count === numCourses, every course was processed and there is no cycle
If count < numCourses, some courses are stuck in a cycle and can never be taken

Key Insight

This is a classic cycle detection problem on a directed graph using topological sort (Kahn's Algorithm)
A valid topological ordering exists if and only if the graph has no cycles
BFS peels off nodes layer by layer — nodes with no incoming edges first, then their dependents

Time

O(V + E) where V = numCourses and E = number of prerequisites

Space

O(V + E) for the graph and in-degree array

Solution Code

Course Schedule II