Course Schedule
Asked at Amazon, Apple, Meta, Walmart
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.
Asked At
| 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 → |
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.
Visual walkthrough for n=3, prereqs=[[1,0],[2,1]]:
Graph: 0→1→2
BFS: in-degrees=[0,1,1]. Queue=[0].
Process 0: count=1. Decrement 1→0. Queue=[1].
Process 1: count=2. Decrement 2→0. Queue=[2].
Process 2: count=3. Done. 3==3 → true.
For n=2, prereqs=[[1,0],[0,1]]:
Graph: 0→1→0 (cycle!)
BFS: in-degrees=[1,1]. Queue=[]. Count=0. 0!=2 → false.
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).
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
from 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Course Schedule?
Course Schedule is asked at Amazon, Apple, Meta, Walmart. 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.