The problem
Same setup as Course Schedule, but return one valid order in which to take all courses, or an empty list if it’s impossible.
Input: n = 6, prerequisites 1-0, 2-0, 3-1, 3-2, 4-3, 5-2 Output: [0, 1, 2, 3, 5, 4]
Picture it
Same course map. Every time a course becomes free (no unfinished prerequisites), we add it to the timetable. The order in which courses are taken is the answer. If the timetable ends up shorter than n, some courses were in a loop.
How to recognise it
- Like Course Schedule, but you must produce an order, not only say whether one exists.
- "Must come before" rules form a directed graph, and any order that respects every rule is accepted.
- An empty answer signals a cycle, so the algorithm must notice cycles as well as build the order.
- With up to 2,000 courses, trying orderings (2,000! of them) is out of the question, and even 12 courses already have 479 million.
Start with brute force
Build the order one course at a time: scan all courses, take the first one that has not been taken and whose prerequisites are all taken, and repeat. If a full scan finds nothing, there is a cycle.
def find_order_brute(n, prerequisites):
needs = defaultdict(list)
for course, need in prerequisites:
needs[course].append(need)
taken, done = [], set()
while len(taken) < n:
for c in range(n):
if c not in done and all(b in done for b in needs[c]):
taken.append(c)
done.add(c)
break
else:
return []
return taken
Each of the n rounds scans up to V courses and all their prerequisites, so time is O(V·(V + E)): about 1.4 × 10^7 steps for 2,000 courses and 5,000 rules, but about 10^10 for 10^5 of each. Space is O(V + E).
From brute force to the idea
- Find the waste. Every round rechecks courses whose situation has not changed. Only courses that depend on the course just taken can become free.
- Track unmet prerequisites.
indeg[c]counts them, andnxt[need]lists the courses that wait forneed. - Queue the free ones. Every course with
indeg == 0goes into the queue. Taking one means appending it totaken. - Update only the neighbours. When course
cis taken, decreaseindegfor each course innxt[c]. Any that drops to 0 is now free and is queued. - The order is the answer.
takenalready respects all rules, because a course is added only after all its prerequisites were. Iflen(taken) < n, some courses sit on a cycle and the function returns[].
The key idea: the order in which Kahn's algorithm takes courses is itself a valid schedule.
The key idea
Topological order from Kahn’s algorithm; length < n means a cycle.
Python solution
def find_order(n, prerequisites):
indeg = [0] * n; nxt = defaultdict(list)
for course, need in prerequisites:
nxt[need].append(course); indeg[course] += 1
q = deque(c for c in range(n) if indeg[c] == 0)
taken = []
while q:
c = q.popleft()
taken.append(c)
for d in nxt[c]:
indeg[d] -= 1
if indeg[d] == 0:
q.append(d)
return taken if len(taken) == n else []LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict, deque
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(V·(V + E)): n rounds, each scanning courses and their prerequisites | O(V + E): the lists and the done set |
| Kahn's algorithm (shown code) | O(V + E): each course is queued once and each rule is processed once | O(V + E): the adjacency lists, in-degrees, queue and result |
Edge cases
- No rules (
n = 3,[]): returns[0, 1, 2]. - One chain (
n = 2,[[1, 0]]): returns[0, 1], because course 0 must come first. The pair[a, b]means "a needs b". - A cycle (
[[0,1],[1,0]]): returns[]. - A cycle plus free courses: the free ones are taken, but the length check still fails, so the result is
[], not a partial order. - Several valid orders: any is accepted. For
[[1,0],[2,0],[3,1],[3,2]]the shown code gives[0, 1, 2, 3]. n = 0: returns[], the same as the "impossible" answer.dequeanddefaultdictmust be imported.
Common mistakes
- Returning the partial list when a cycle exists, instead of
[]. - Reversing the pair, which produces an order where each course comes before its prerequisite.
- Returning
taken[::-1], which is valid only for the opposite arrow convention. - Keeping only courses that appear in a rule, so independent courses are missing.
- Marking a course taken when its first prerequisite is done instead of its last.
Of all valid orders, return the one that is smallest when compared as lists (so course 0 comes as early as possible, then course 1, and so on). Return [] if impossible. Describe what changes, then write it if you like.
Compare with our answer
Kahn's algorithm stays the same, but the free courses go into a min-heap instead of a plain queue, so the smallest free course is always taken next.
import heapq
def smallest_order(n, prerequisites):
indeg = [0] * n
nxt = defaultdict(list)
for course, need in prerequisites:
nxt[need].append(course)
indeg[course] += 1
heap = [c for c in range(n) if indeg[c] == 0]
heapq.heapify(heap)
taken = []
while heap:
c = heapq.heappop(heap)
taken.append(c)
for d in nxt[c]:
indeg[d] -= 1
if indeg[d] == 0:
heapq.heappush(heap, d)
return taken if len(taken) == n else []
smallest_order(4, [[0, 3], [1, 2]]) is [2, 1, 3, 0], because 3 and 2 must come before 0 and 1. Time O((V + E) log V), space O(V + E).
A strong answer mentions: replacing the queue with a heap, that each free course is chosen greedily as the smallest, and the extra log factor.
1. Database migrations come with rules "migration A must run before B". You must print one order that runs them all, or fail if the rules contradict each other. Which approach fits best?
Taking migrations that have no unmet dependencies yields a valid order and exposes contradictions as leftovers. Names, BFS order and unions do not respect the direction of the rules.
2. Why does the shown solution run in O(V + E) time?
Every course enters and leaves the queue once, and each rule is touched exactly once when its prerequisite is taken. There is no sort, and the loop continues until the queue is empty.
3. A learner changes the last line to return taken[::-1] when a valid order exists. Which input still returns a valid order?
Reversing is wrong whenever some rule exists, because the reversed order puts a course before its prerequisite. With no rules, every order is valid, including the reversed one.
Score 60% or more and the lesson is marked complete.