Practice Course Schedule
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Course Schedule
Problem Statement
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. Return true if you can finish all courses. Otherwise, return false.
Source: Course Schedule on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
numCourses = 2, prerequisites = [[1,0]]
true
# Example 2
numCourses = 2, prerequisites = [[1,0],[0,1]]
false
Constraints
How to solve Course Schedule
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
You can finish all courses exactly when the prerequisite graph has no directed cycle. Repeatedly taking any course whose prerequisites are all done, and tracking how many you managed to take, detects a cycle as leftover courses that never become available.
Why brute force is not enough
Repeatedly scanning all courses for one whose prerequisites are all satisfied is O(V * (V + E)), and running a separate cycle check from every course costs about as much. With 2000 courses and 5000 prerequisites that is tens of millions of steps, workable but far from the linear bound expected.
Approach
- Build an adjacency list with an edge from each prerequisite to the course it unlocks, and count each course's incoming edges (its number of prerequisites).
- Seed a queue with every course whose incoming count is zero; these can be taken immediately.
- Pop a course, count it as taken, and decrement the incoming count of every course it unlocks. Any course whose count drops to zero joins the queue.
- The invariant is that every queued course has all prerequisites already taken. When the queue empties, compare taken courses to numCourses: equal means a valid order exists; fewer means a cycle blocked the rest.
Walkthrough of Example 2
numCourses = 2, prerequisites = [[1,0],[0,1]] → false
- Pair [1,0] adds an edge 0 to 1 and pair [0,1] adds an edge 1 to 0. Course 0 has one incoming edge and course 1 has one.
- No course has zero incoming edges, so the queue starts empty.
- The processing loop never runs and the taken count stays 0.
- 0 is less than 2, so some course can never be unlocked; return false. The two courses each wait on the other, which is a cycle.
Time and space
Time O(V + E) · Space O(V + E). V is numCourses and E is the number of prerequisite pairs; building the graph and processing each edge once is linear, and the adjacency list dominates memory.
Interview pitfalls
- Using depth-first search with only visited and unvisited states; a diamond-shaped dependency gets reported as a cycle. You need a third in-progress state.
- Reversing the edge direction; it still detects cycles here but breaks the ordering variant (Course Schedule II).
- Forgetting courses with no prerequisites and no dependents; they must still be seeded and counted.
- A single course with no prerequisites should return true; an empty prerequisites list means all courses are independent.
- Counting the queue size instead of popped courses, or decrementing counts before the full graph is built.
Follow-up questions interviewers ask
- Return a valid course order (Course Schedule II); what changes in the output handling?
- Determine the minimum number of semesters if any number of courses can be taken per semester.
- How would you identify the actual courses involved in the cycle to report them?
Further reading on the technique: Topological sorting
Related LeetCode Problems
Practice more problems similar to Course Schedule.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.