207. Course Schedule
Asked at Amazon, Apple, Meta, Walmart and 4 more
Difficulty
Medium
Time
O(V + E)
Space
O(V + E)
Pattern
Depth-First Search
Companies
8
Problem
You must finish numCourses courses, numbered from 0 to numCourses - 1. Some courses have requirements: the pair [a, b] means you must finish course b before you can start course a.
Think of each course as a node in a directed graph, and each requirement as an arrow b → a. You can finish everything only if there is a valid order to take the courses. Such an order exists exactly when the graph has no cycle. A cycle means a deadlock: course x needs y, y needs z, and z needs x — nobody can start.
Return true if all courses can be finished, and false if some cycle makes it impossible.
Prerequisites as arrows
Constraints
- ●
1 <= numCourses <= 2000 - ●
0 <= prerequisites.length <= 5000 - ●
prerequisites[i].length == 2 - ●
0 <= ai, bi < numCourses - ●
All the pairs prerequisites[i] are unique.
Examples
numCourses = 2, prerequisites = [[1,0]]truenumCourses = 2, prerequisites = [[1,0],[0,1]]falseAsked At
8 companies| Company | Difficulty | |
|---|---|---|
| Amazon | Medium | View all Amazon questions → |
| Apple | Medium | View all Apple questions → |
| Meta | Medium | View all Meta questions → |
| Walmart | Medium | View all Walmart questions → |
| Goldman Sachs | Medium | View all Goldman Sachs questions → |
| TikTok | Medium | View all TikTok questions → |
| Anduril | Medium | View all Anduril questions → |
| Snowflake | Medium | View all Snowflake questions → |
How to Think About It
Model courses as a directed graph. If there is a cycle, you cannot finish all courses (A requires B requires A — deadlock).
Approach 1 — BFS (Kahn's algorithm): compute in-degrees, process nodes with in-degree 0. If you process all n nodes, no cycle. If fewer, cycle exists.
Approach 2 — DFS: three states per node: unvisited (0), visiting (1), visited (2). If you hit a node in "visiting" state during DFS, you found a back-edge — that's a cycle.
Why DFS works for cycle detection: during DFS, if you're currently exploring a path and you revisit a node on that path, there's a cycle. The "visiting" state tracks the current DFS path.
Optimal Approach
Approach 1 — BFS (Kahn's):
Step 1: Build adjacency list and in-degrees.
Step 2: Queue all nodes with in-degree 0.
Step 3: Process queue, decrementing neighbor in-degrees.
Step 4: If count == n → true (no cycle). Else → false.
Approach 2 — DFS:
Step 1: Build adjacency list.
Step 2: For each unvisited node, run DFS with three states.
Step 3: If DFS encounters a "visiting" node → cycle → return false.
Step 4: If all nodes visited → true.
Time: O(V + E). Space: O(V + E).
Kahn's algorithm: peel off in-degree 0 nodes
What Trips People Up in Real Interviews
Confusing "prerequisite" direction. If course A requires course B, the edge is B → A (B must come before A). Getting the direction wrong breaks the cycle detection.
Using DFS without tracking the recursion stack. You need to distinguish between "currently visiting" and "already visited" to detect cycles. Three states: unvisited, visiting, visited.
Not handling the case where there are no courses (n = 0). Return true — vacuously satisfiable.
Forgetting that some courses might have no prerequisites. They should be included in the topological order.
Not handling self-loops. If a course has itself as a prerequisite [A, A], that's a cycle of length 1. The algorithm catches this, but some implementations skip self-referencing edges.
Solution Code
O(V + E) timefrom collections import deque
def canFinish(numCourses, prerequisites):
adj = [[] for _ in range(numCourses)]
in_degree = [0] * numCourses
for dest, src in prerequisites:
adj[src].append(dest)
in_degree[dest] += 1
q = deque([i for i in range(numCourses) if in_degree[i] == 0])
count = 0
while q:
node = q.popleft()
count += 1
for neighbor in adj[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
q.append(neighbor)
return count == numCoursesFrequently Asked Questions
What is the Course Schedule problem?
There are a total of n courses with prerequisites. Determine if it is possible to finish all courses. This is the cycle-detection version of the course scheduling problem — a core graph problem.
How do you solve Course Schedule?
The optimal approach runs in O(V + E) time and O(V + E) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Course Schedule?
Course Schedule is asked at Amazon, Apple, Meta, Walmart, Goldman Sachs, TikTok, Anduril, Snowflake. It is a medium difficulty problem.
What are common mistakes on Course Schedule?
- Confusing "prerequisite" direction. If course A requires course B, the edge is B → A (B must come before A). Getting the direction wrong breaks the cycle detection.
- Using DFS without tracking the recursion stack. You need to distinguish between "currently visiting" and "already visited" to detect cycles. Three states: unvisited, visiting, visited.
- Not handling the case where there are no courses (`n = 0`). Return `true` — vacuously satisfiable.
- Forgetting that some courses might have no prerequisites. They should be included in the topological order.
- Not handling self-loops. If a course has itself as a prerequisite [A, A], that's a cycle of length 1. The algorithm catches this, but some implementations skip self-referencing edges.