Strip away the course-catalog wording and the LeetCode problem called Course Schedule (problem 207) is asking a single question: do these prerequisites contain a cycle? You’re given numCourses and a list of pairs where [a, b] means you must finish course b before course a. Return true if some order lets you take everything. If X needs Y, Y needs Z, and Z needs X, no order works and the answer is false. That loop is the only thing standing between you and a valid schedule.
Once you read it as a directed graph, where every prerequisite is an edge, the whole thing collapses into two well-worn techniques. A directed graph has a valid ordering of its nodes exactly when it has no cycle. That ordering has a name, topological order, and producing one (or proving none exists) is what the interviewer is actually checking.
Get the edge direction right first
The pairs are edges, so the first decision is which way they point. Read [a, b] as “b unlocks a” and draw the edge from b to a. Get this backwards and your code will look correct and return garbage, which is one of the most common ways people lose this question under time pressure. Build an adjacency list from that and you’re ready for either approach.
Kahn’s algorithm: peel off the courses with nothing blocking them
The intuition matches how you’d really plan a semester. Find every course with no remaining prerequisites, take those, then cross them off everyone else’s prerequisite list. Some new courses now have nothing blocking them, so take those next. Keep going. If you run out of zero-prerequisite courses before you’ve taken all of them, the leftovers are tangled in a cycle.
The bookkeeping for that is the in-degree: for each node, how many edges point into it. Courses with in-degree zero go in a queue. Pop one, and for each course it unlocks, drop that course’s in-degree by one; when a count hits zero, it joins the queue.
from collections import deque
def can_finish(num_courses, prerequisites):
graph = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
indegree[course] += 1
queue = deque(c for c in range(num_courses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in graph[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return taken == num_coursesIf taken equals numCourses, every node came off the queue and the graph is acyclic. If it falls short, the missing courses form at least one cycle and never reach in-degree zero. Runtime is O(V + E): you touch every course once and walk every edge once. Space is the same, dominated by the adjacency list.
DFS with three colors: catch the back edge
The recursive version finds a cycle directly. Walk the graph depth-first, and a cycle shows up as an edge pointing back to a node you’re still in the middle of visiting. The trap here is that a plain visited-or-not boolean is not enough. You need three states.
White means untouched. Gray means the node is on the current recursion stack, entered but not yet finished. Black means fully explored, every path out of it already checked. The moment you reach a gray node, you’ve found an edge back into the active path, which is a cycle. Reaching a black node is fine, it’s already cleared.
WHITE, GRAY, BLACK = 0, 1, 2
def can_finish(num_courses, prerequisites):
graph = [[] for _ in range(num_courses)]
for course, prereq in prerequisites:
graph[prereq].append(course)
color = [WHITE] * num_courses
def has_cycle(node):
color[node] = GRAY
for nxt in graph[node]:
if color[nxt] == GRAY:
return True
if color[nxt] == WHITE and has_cycle(nxt):
return True
color[node] = BLACK
return False
return all(
not has_cycle(c)
for c in range(num_courses)
if color[c] == WHITE
)People who track only a single visited set tend to flag cycles that aren’t there. A node you finished exploring down one branch is perfectly legal to revisit from another branch in an acyclic graph; picture a diamond where two paths reconverge. Black is what separates “seen and safe” from “seen and still open.” Same O(V + E) cost, but watch the recursion depth. A long prerequisite chain can overflow the stack, and some interviewers will steer you toward the iterative version for that exact reason.
Course Schedule II: now hand back the order
Problem 210 is the same graph with one change to the ask. Instead of true or false, return an actual order to take the courses, or an empty array if it can’t be done. Kahn’s algorithm gives you this almost for free, because the sequence in which nodes leave the queue is already a topological order. Append each course as you pop it.
from collections import deque
def find_order(num_courses, prerequisites):
graph = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, prereq in prerequisites:
graph[prereq].append(course)
indegree[course] += 1
queue = deque(c for c in range(num_courses) if indegree[c] == 0)
order = []
while queue:
course = queue.popleft()
order.append(course)
for nxt in graph[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
return order if len(order) == num_courses else []If a cycle exists, fewer than numCourses nodes make it out, the order comes up short, and you return the empty list the problem wants. The DFS variant produces an order too, by pushing each node onto a list as it turns black and reversing at the end, but the queue-based version is easier to narrate out loud, which counts for a lot when someone is watching you type.
The follow-ups that separate a pass from a strong pass
Solving 207 cleanly is table stakes. The signal comes from what you do when the interviewer twists it, and a few twists come up again and again.
Return the lexicographically smallest valid order. Swap the plain queue for a min-heap so you always take the smallest available course id next. The shape of Kahn’s algorithm doesn’t change, only the structure deciding what to pop, and runtime picks up a log factor from the heap.
Name the courses that sit in the cycle, rather than only flagging that one exists. After Kahn’s finishes, any course still carrying a nonzero in-degree is inside a cycle or downstream of one. That set is your answer, and it’s a cheap addition once the main loop is written.
What if prerequisites repeat a pair, or a course requires itself? A self-loop [a, a] is an instant cycle, and a decent solution handles it with no special case because that in-degree never drops to zero. Duplicate edges inflate in-degrees but don’t break correctness as long as you decrement once per edge. Saying this before the interviewer pokes at it shows you’ve thought about the input.
Why this pattern keeps showing up
Topological sort looks academic until you notice it running everywhere. A build tool compiling source files has to respect include dependencies. A package manager resolving installs runs the same in-degree dance, and a circular dependency is a cycle it has to report rather than spin on forever. Spreadsheet engines order cell recalculation this way. The reason Course Schedule, Course Schedule II, and the meaner Alien Dictionary all cluster in company question banks is that they map onto real dependency-resolution work, so the interviewer gets to watch you model a vague requirement as a graph and then pick the right traversal.
If you keep only one of the two solutions in working memory, make it Kahn’s. It answers the yes/no question, hands back a valid order, extends to the lexicographic variant with a one-line swap to a heap, and points straight at the courses caught in a cycle, all without recursion to manage. The DFS coloring approach still earns its keep, since the three-state idea reappears in deadlock detection and in spotting back edges anywhere, and an interviewer who tells you to solve it without a queue is fishing for exactly that. The shortcut that sinks people is the single visited flag, so if you remember nothing else about the recursive version, remember why gray and black have to be different states.
Drill the patterns next:
