Course Schedule medium
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] = [a_i, b_i] indicates that you must take course b_i first if you want to take course a_i.
Return true if you can finish all courses. Otherwise, return false.
Examples
> Case 1:
numCourses = 2, prerequisites = [[1, 0]]
Output: true
Explanation: take course 0, then course 1.
> Case 2:
numCourses = 2, prerequisites = [[1, 0], [0, 1]]
Output: false
Explanation: courses 0 and 1 depend on each other — impossible.Constraints
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= a_i, b_i < numCourses- All
[a_i, b_i]pairs are distinct.
State design
A cycle-detection problem in disguise:
- Nodes:
numCoursescourses. - Edges:
[a, b]meansb → a(takebbeforea). - Question: is the resulting graph a DAG?
Kahn’s count-check is the cleanest solution.
Code
The edge direction trap. LeetCode writes [a, b] as “to take a, you need b first.” The corresponding edge is b → a, NOT a → b. Half of all “Course Schedule wrong answer” bugs come from flipping this. Read the problem statement word by word.
Alternative — three-color DFS
For completeness, the DFS approach:
O(V + E) time and space. Same asymptotics; recursion depth caveat applies (default Python recursion limit can be hit on adversarial inputs with numCourses = 2000).
Analysis
- Time:
O(V + E) = O(numCourses + len(prerequisites)). - Space:
O(V + E).
Same skin
- Course Schedule II — same setup, return the order instead of a boolean.
- Course Schedule IV — preprocess to answer “is X a prerequisite of Y?” queries.
- Find Eventual Safe States — reverse-graph Kahn’s.
- Detect Cycle in a Directed Graph — generic version of this same problem.
This is the entry point to the entire topo-sort family. Get the template right here and the next nine problems are 80% the same code.