Course Schedule II
Problem statement
There are numCourses courses, numbered 0 to numCourses - 1. Each pair [a, b] in prerequisites means you must finish course b before you can start course a.
Return an order in which you can take all the courses. If several orders work, return any of them. If no order works — because some courses depend on each other in a circle — return an empty list.
This is exactly the question a deploy tool answers before a rollout: given which services depend on which, in what order should they start? A circular dependency means there is no safe order.
Examples
Example 1
Input: numCourses = 2, prerequisites = [[1,0]]
Output: [0,1]
Explanation: Course 1 needs course 0 first, so the only valid order is 0 then 1.
Example 2
Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]
Explanation: Course 0 has no prerequisites, courses 1 and 2 each need 0, and course 3 needs both 1 and 2. So 0 comes first and 3 comes last; [0,2,1,3] is just as correct.
Example 3
Input: numCourses = 1, prerequisites = []
Output: [0]
Explanation: There is only one course and nothing to wait for, so it is taken on its own.
Hints
Approach
Optimal: DFS with three states
Intuition
Think about a single course. Before you can write it down, all its prerequisites must already be written down. So, to place course c: first place each of its prerequisites (the same way, recursively), then write c. This is a depth-first search (DFS), and because each course is written only after its prerequisites finish, the list comes out in a valid order.
To catch cycles, give each course one of three states: unvisited, in progress (we are still placing its prerequisites), or done. If the DFS reaches a course that is in progress, we've walked in a circle back to a course that is waiting on us — a cycle — so return []. A done course is already written down and can be skipped.
Steps
- Build
needs[c]: the prerequisites of each course. Set every state to unvisited. - Define
place(c):- If
cis in progress, returnfalse(cycle). - If
cis done, returntrue. - Mark
cin progress. Callplace(p)for eachpinneeds[c]; if any returnsfalse, returnfalse. - Mark
cdone, add it toorder, and returntrue.
- If
- Call
place(c)for every coursecfrom 0 up. If any call returnsfalse, return[]. - Return
order.
Dry run
Example 2: needs = {0: [], 1: [0], 2: [0], 3: [1, 2]}
| call | what happens | order |
|---|---|---|
| place(0) | no prerequisites → done | [0] |
| place(1) | needs 0 (done) → done | [0, 1] |
| place(2) | needs 0 (done) → done | [0, 1, 2] |
| place(3) | needs 1, 2 (both done) → done | [0, 1, 2, 3] |
Edge case: with [[1,0],[0,1]], place(0) marks 0 in progress and calls place(1), which marks 1 in progress and calls place(0) — 0 is in progress, so it's a cycle → [].
Complexity
Time O(n + E) - Each course is fully explored only once; after that it is marked done and every later visit returns at once. Exploring a course looks at each of its prerequisites once, so every pair is followed once in total. Together that is linear in courses plus pairs, the same as Kahn's.
Space O(n + E) - The prerequisite lists hold all E pairs. The state list and the output are O(n). The recursion can go n calls deep on a long chain, which is why the Python code raises its recursion limit.
import sys
from typing import List
sys.setrecursionlimit(10000) # a chain of 2,000 courses recurses 2,000 deep
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
needs: List[List[int]] = [[] for _ in range(numCourses)]
for course, pre in prerequisites:
needs[course].append(pre)
UNVISITED, IN_PROGRESS, DONE = 0, 1, 2
state = [UNVISITED] * numCourses
order: List[int] = []
def place(c: int) -> bool:
if state[c] == IN_PROGRESS:
return False
if state[c] == DONE:
return True
state[c] = IN_PROGRESS
for p in needs[c]:
if not place(p):
return False
state[c] = DONE
order.append(c)
return True
for c in range(numCourses):
if not place(c):
return []
return order
if __name__ == "__main__":
print(str(Solution().findOrder(2, [[1, 0]])).replace(" ", "")) # [0,1]
print(str(Solution().findOrder(4, [[1, 0], [2, 0], [3, 1], [3, 2]])).replace(" ", "")) # [0,1,2,3]
print(str(Solution().findOrder(1, [])).replace(" ", "")) # [0]RecapThe whole problem in a few lines, for the night before
- Spot it: "in what order can we do tasks with prerequisites?" or "is there a circular dependency?"
- Idea: Kahn's — count missing prerequisites per task, repeatedly take a task with count 0 and lower the counts it unlocks
- Cost: O(n + E) time, O(n + E) space
- Trap: forgetting the cycle check — if fewer than
ntasks were taken, return an empty list - Remember: DFS alternative needs three states (unvisited, in progress, done) to tell a cycle from a shared prerequisite
Interview follow-ups
Return the actual cycle when no order exists.
Use the DFS approach and keep the current path in a list, pushing a course when it goes in progress and popping it when it's done. When you reach a course that is in progress, the cycle is the part of the path from that course to the end. Time and space stay O(n + E). Printing the cycle is what makes a "circular dependency" error message useful.
You can take up to
kcourses at the same time. What's the fewest number of terms?Without the limit
k, run Kahn's in layers: each round takes everything currently in the queue, and the number of rounds is the answer. That is the length of the longest dependency chain. With a limitk, the problem gets much harder in general (it is LeetCode's Parallel Courses II), so say that and fall back to taking up tokready courses per round as a heuristic.New dependencies are added over time. How do you avoid rerunning the whole sort?
When a new pair
b → aarrives andbalready comes beforeain the current order, nothing changes. Otherwise, only the courses between them in the order need to be reshuffled, and a cycle exists ifacan reachb. A simple production approach is to check reachability fromatobfirst (to reject cycles early) and re-sort only when the order actually breaks.
Frequently asked questions
It is an ordering of the nodes of a directed graph where every edge points forward: if b must come before a, then b appears earlier in the list. It exists only when the graph has no cycle. Course schedules, build steps and service start-up orders are all topological sorts.
Both. Courses 1 and 2 each depend only on 0, so either can go first, and the problem accepts any valid order. The code on this page happens to pick the lower-numbered course first. If you want [0,2,1,3], you'd get it from a different queue order or from the "reverse post-order" style of DFS.
Both are O(n + E). Kahn's is iterative, so it never hits a recursion limit, and "the queue ran dry before all courses were taken" is an easy cycle check to explain. DFS is shorter once you know the three-state trick, and it can report the actual cycle. In an interview, pick the one you can explain clearly.
With only "visited", you can't tell two very different cases apart. Reaching a course that's already done is fine — it's a shared prerequisite, like course 0 in Example 2. Reaching a course that's still in progress means you walked in a circle. The third state is what separates "seen before" from "cycle".
Deciding a safe order from a list of dependencies is everywhere in infra. Terraform orders resource creation this way, package managers order installs, build systems order compile steps, and orchestrators order service start-up. Detecting a circular dependency before a rollout is the same cycle check.
