207. Course Schedule
mediumGiven prerequisites between courses, decide whether you can finish all of them. The textbook cycle-detection-in-a-directed-graph problem — either Kahn's BFS topological sort or DFS with three colors works.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Problem
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.
Constraints
1 <= numCourses <= 20000 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesAll the pairs prerequisites[i] are unique.
Examples
Example 1
numCourses = 2, prerequisites = [[1,0]]trueExplanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
Example 2
numCourses = 2, prerequisites = [[1,0],[0,1]]falseExplanation: To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
Hints
Progressive — try the first before opening the next.
Hint 1
Model courses as nodes and prerequisites as directed edges. What property of that graph makes the schedule possible?
Hint 2
If the graph has no directed cycle, a valid order exists (topological sort). If it has a cycle, no order works.
Hint 3
Kahn's algorithm: compute in-degrees, push every 0-in-degree node into a queue, pop and decrement neighbors. If you pop numCourses nodes total, no cycle. Otherwise return false.
Solution approach
Reveal approach
Build an adjacency list from prerequisites — edge b -> a means b must come before a — and an in-degree array. Initialize a queue with every node whose in-degree is 0. Process the queue: pop a node, increment a popped counter, and decrement the in-degree of every neighbor; when a neighbor's in-degree hits 0, enqueue it. After the queue empties, return popped == numCourses. If a cycle exists, those cycle nodes' in-degrees never reach 0 so they're never enqueued. The DFS alternative uses three colors: white (unvisited), gray (in current path), black (fully done) — gray-on-gray means cycle. O(V + E) time, O(V + E) space for the adj list.
Complexity
- Time
- O(V + E)
- Space
- O(V + E)
Related patterns
- topological-sort
- dfs
- bfs
- graph
Related problems
- 210. Course Schedule II
- 1462. Course Schedule IV
- 269. Alien Dictionary
Asked at
Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).
- Amazon
- Meta
- Microsoft
- Apple
Practice these live with InterviewChamp.AI
Drill Course Schedule and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →