Course Schedule
Course Schedule is LeetCode 207 (Medium). You have to take numCourses courses, labelled 0 to numCourses - 1. The list prerequisites holds pairs [a, b], and each pair means course b must be finished before course a can start.
- Return
trueif some order of the courses satisfies every prerequisite. - Return
falseif the course prerequisites make that impossible.
You only report whether an order exists; producing it is the follow-up problem. With up to 2,000 courses and 5,000 pairs, the solution should be linear in courses plus pairs.
- 1 <= numCourses <= 2000
- 0 <= prerequisites.length <= 5000
- prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
- All the pairs prerequisites[i] are unique.
Intuition
Course Schedule is cycle detection in disguise. Draw each course as a node and each prerequisite [a, b] as an arrow b → a. If the arrows form a cycle, each course on it waits on another one on it, so none can ever be taken first and the answer is false.
If there is no cycle, some course always has no unmet prerequisite. Take it, remove its arrows, and another course becomes free; repeating this takes every course. That peeling order is the course schedule topological sort, and Kahn's algorithm performs it by tracking how many prerequisites each course is still waiting on.
Tasks with "must come before" rules are a directed graph, and "can all tasks be done?" is "is the graph acyclic?". Build systems, package installs, spreadsheet formulas and job pipelines all reduce to this. If the question asks for an actual order, it is Course Schedule II (210), the same code returning the order list.
Approach
Before reading on, decide which way the arrow for [a, b] should point, and what number a course needs to reach before it can be taken. Aim for O(V + E).
Build the graph and in-degrees
For each pair [course, pre]:
graph[pre].append(course): the arrow goes from the prerequisite to the course it unlocks.indegree[course] += 1: one more prerequisite that course is waiting on.
Seed the queue with free courses
Every course with indegree == 0 can be taken immediately. Put all of them in a queue. If none exist, every course waits on another and there must be a cycle. In the course schedule Python code the queue is a collections.deque, so popping from the front is O(1).
Take courses and release their dependents
- Pop a course and add 1 to
taken. - For each course it unlocks, decrement that course's in-degree.
- When an in-degree reaches 0, all its prerequisites are done: push it onto the queue.
Why counting taken courses detects a cycle
Return taken == numCourses. Courses on a cycle never reach in-degree 0, because the arrow into the cycle's first course comes from a course that is itself stuck. So they are never taken, and the count falls short.
Course Schedule solution in Python | C++ | Java
[a, b] means b must come before a, so draw the arrow b → a. A course's in-degree is how many prerequisites it still waits on. The schedule is possible exactly when this graph has no cycle.[a, b] means b must come before a, so draw the arrow b → a. A course's in-degree is how many prerequisites it still waits on. The schedule is possible exactly when this graph has no cycle.[a, b] means b must come before a, so draw the arrow b → a. A course's in-degree is how many prerequisites it still waits on. The schedule is possible exactly when this graph has no cycle.Common pitfalls
Pointing the arrow the wrong way
for course, pre in prerequisites:
graph[course].append(pre)
indegree[course] += 1for course, pre in prerequisites:
graph[pre].append(course)
indegree[course] += 1The edge list and the in-degree must agree on direction. Mixed up, taking a course lowers the in-degree of its own prerequisite, and valid schedules get reported as impossible.
Using a plain visited set in the DFS version
if node in visited:
return False # treated as a cycleif state[node] == VISITING:
return False # back edge: a real cycle
if state[node] == DONE:
return TrueIn a directed graph a node can be reached twice without a cycle, as in a diamond 0→1→3, 0→2→3. Only a node still on the current DFS path means a cycle, so DFS needs three states, not two.
Forgetting courses with no prerequisites
graph = {}
for course, pre in prerequisites:
graph.setdefault(pre, []).append(course)graph = [[] for _ in range(numCourses)]
Courses that appear in no pair still count. Building nodes only from the pairs leaves them out, so taken can never reach numCourses.
Edge cases
[a, a]Course a waits on itself, so its in-degree never drops to 0. The count falls short: false.
The seed step picks up the free courses of every group at once; no separate loop per component is needed.
Complexity
numCourses and E is the number of prerequisite pairs. This course schedule LeetCode solution is linear in both: every course enters the queue at most once and every edge is relaxed once. The adjacency list holds E entries.Kahn's BFS vs DFS cycle detection
Both are standard answers to LeetCode 207 and run in the same time. They differ in what state they keep and what they give you for free.
| Kahn's algorithm (BFS) | DFS with three colours | |
|---|---|---|
| State per course | in-degree count | unvisited / visiting / done |
| Cycle signal | taken < numCourses at the end | reaching a node that is still visiting |
| Order for free | yes: the pop order (Course Schedule II) | yes: reverse post-order |
| Recursion | none | depth up to V; can overflow on long chains |
| Easiest to explain in an interview | counting prerequisites | back edges |
Course Schedule FAQ
How do you solve Course Schedule (LeetCode 207)?
- Model: each course is a node;
[a, b]is a directed edge b → a. - Key fact: all courses can be finished if and only if the graph has no cycle.
- Algorithm: Kahn's topological sort. Compute in-degrees, queue every course with in-degree 0, pop, count, and decrement each dependent; queue it when it reaches 0.
- Answer:
taken == numCourses. - Complexity: O(V + E) time and space.
- Example: 2 courses with
[[1,0],[0,1]]both start at in-degree 1, nothing is ever taken, so the answer isfalse.
What is the difference between Course Schedule and Course Schedule II?
Course Schedule (207) only asks whether an order exists. Course Schedule II (210) asks for the order itself. The code is the same, except it records each popped course in a list and returns that list, or [] if a cycle leaves courses out.
What is the time complexity of Course Schedule?
O(V + E), where V is the number of courses and E the number of prerequisite pairs. Building the graph touches every pair once, and the BFS processes each course and each edge once.