Course Schedule
Problem statement
You need to take numCourses courses, numbered 0 to numCourses - 1. Some courses require another course to be finished first — a pair [a, b] in prerequisites means you must take course b before you're allowed to take course a.
Given all the prerequisite pairs, return true if it's possible to finish every course, or false if the requirements make that impossible.
This is the same shape as service startup ordering: service A might need service B to already be up before it can start, and the real question is whether that whole web of "needs" can ever be satisfied, or whether two or more services end up needing each other in a loop that can never resolve.
Examples
Example 1
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: course 1 needs course 0 first, so take course 0, then course 1 — both get finished with no conflict.
Example 2
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: course 1 needs course 0, but course 0 also needs course 1 — each is stuck waiting on the other, so neither can ever be taken first.
Hints
Approach
Optimal: 2 (Kahn's algorithm — BFS topological sort
Intuition
Instead of exploring one course's chain of requirements at a time, work outward from whatever's already available: any course with zero remaining prerequisites can be taken right now. Take it, and for every course that depended on it, reduce its remaining-requirement count by one — if that count hits zero, it just became available too. Keep taking available courses this way. If every course eventually gets taken, there was no cycle; if the queue runs dry while some courses are still waiting, those leftover courses can only be waiting on each other in a loop.
Steps
- Build an adjacency list: for each prerequisite
[course, need], add a forward edge fromneedtocourse(finishingneedunlockscourse). - Count each course's in-degree: how many prerequisites still block it.
- Put every course with in-degree
0into a queue — these can be taken immediately. - While the queue isn't empty, take a course out, count it as taken, and for every course it unlocks, decrease that course's in-degree by one.
- If a course's in-degree reaches
0, add it to the queue. - Once the queue is empty, return
trueonly if the number of courses taken equalsnumCourses.
Dry run
numCourses = 2, prerequisites = [[1,0],[0,1]]
Forward edges: 0 → 1 (finishing 0 unlocks 1), 1 → 0 (finishing 1
unlocks 0). In-degrees: course 0 has in-degree 1 (from course 1), course 1
has in-degree 1 (from course 0).
| step | queue | taken | action |
|---|---|---|---|
| start | [] (neither has in-degree 0) | 0 | nothing to enqueue at all |
The queue starts empty, since both courses have in-degree 1 and neither
ever reaches 0 — each is only unlocked by the other, which never gets
taken. taken stays at 0, which doesn't equal numCourses (2), so the
answer is false.
Edge cases: with no prerequisites at all, every course starts at in-degree 0 and the queue begins with everything already in it; a chain where each course unlocks exactly the next one processes one course per step, in order, until the whole chain is taken.
Complexity
Time O(V + E) - Every course enters the queue at most once, and every prerequisite edge is examined exactly once when its source course is processed, so the total work is proportional to V + E, the same as the DFS approach.
Space O(V + E) - the adjacency lists, the in-degree array, and the queue, which in the worst case holds every course with no prerequisites at once.
from collections import deque
class Solution:
def canFinish(self, numCourses: int, prerequisites: list[list[int]]) -> bool:
adjacency = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, need in prerequisites:
adjacency[need].append(course)
indegree[course] += 1
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in adjacency[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return taken == numCourses
if __name__ == "__main__":
print(str(Solution().canFinish(2, [[1, 0]])).lower()) # true
print(str(Solution().canFinish(2, [[1, 0], [0, 1]])).lower()) # falseRecapThe whole problem in a few lines, for the night before
- Spot it: "can all of these be finished/scheduled" with
[a, b]meaningadepends onb - Idea: model as a directed graph and check for a cycle — no cycle means a valid order exists
- Cost: O(V + E) time and space (V courses, E prerequisites); naive repeated-sweep check: O(V·(V+E))
- Trap: using a single visited flag in DFS instead of distinguishing "on the current path" from "already cleared" — that's the only way to actually catch the cycle
Interview follow-ups
What if you also needed to return *one valid order* to take the courses in, not just whether it's possible?
Both approaches already build this along the way. In Kahn's algorithm, append each course to a result list at the moment it's dequeued — the resulting list is a valid order, since a course can't be dequeued until every prerequisite ahead of it already has been. In DFS, appending a course to the front of a result list right after it's marked
2(cleared) produces the same kind of valid order, just discovered in the reverse direction.The prerequisite list is enormous and arrives incrementally — new prerequisite pairs keep getting added to a live system. What would you do?
Adding one new edge only risks creating a cycle through that specific edge, so rather than rechecking the whole graph, check whether the new edge's target can already reach the new edge's source (a single traversal from one node, not the whole graph). If it can, this one addition would close a loop and should be rejected; if not, it's safe to add. This turns an O(V+E) full recheck per addition into one bounded search per addition instead.
What if prerequisites came with weights (some courses take longer than others), and you needed the fastest possible schedule assuming courses without a dependency between them can run in parallel?
The cycle check itself is unchanged — a cycle still makes the whole schedule impossible regardless of weights. Once you know it's acyclic, computing the fastest possible finish time becomes a longest-path problem on the same graph, using Kahn's ordering: process courses in topological order, and for each one, its earliest finish time is its own duration plus the maximum finish time among everything it depends on. That's still O(V + E), just doing slightly more arithmetic per course instead of a simple boolean check.
Frequently asked questions
Swap "course" for "service", "package", or "database migration" and this is exactly startup-ordering and dependency-resolution: can every service in a deployment come up given what each one depends on, and is there a circular dependency (A needs B, B needs A) that would deadlock the rollout forever? Build tools, package managers, and Kubernetes-style dependent workloads all run some version of this same cycle check before doing anything.
Because the underlying fact being checked — whether the dependency graph has a cycle — doesn't depend on the order courses are visited in, only on the graph's actual structure. DFS finds a cycle by noticing it revisits a course still active on the current exploration path; BFS finds the same fact by noticing some courses never reach zero remaining prerequisites. Different bookkeeping, same underlying graph property, same O(V + E) cost.
A plain visited flag can't tell the difference between "this course is still being actively explored right now" and "this course was fully explored earlier and is safe." Both look like "already seen" with only two states, but only the first one signals a cycle. The middle state — "on the current path" — is what lets the algorithm tell those two very different situations apart.
It means that specific course, and everything else stuck with it, only had prerequisites pointing back into that same stuck group — none of them ever reached zero required prerequisites, because they were all still waiting on each other. That leftover group is precisely the cycle (or the set of courses downstream of one), even though Kahn's algorithm never explicitly names which courses form the loop.
