The problem
There are n courses. Each prerequisite pair “a needs b” means you must take b before a. Can you finish all courses? (Impossible only if the requirements form a loop.)
Input: n = 4, prerequisites 1-0, 2-0, 3-1, 3-2 (“1 needs 0”, …) Output: true
Picture it
Picture each course as a circle with arrows from a course to the courses that need it. A course with no remaining prerequisites can be taken right now. Take it and cross out its arrows; that may free up other courses. If we end up taking every course, it’s possible. If some courses are stuck waiting on each other (a loop), it isn’t.
How to recognise it
- Items with "must come before" rules: courses, build steps, tasks with dependencies.
- The rules form a directed graph, and the question is whether an order exists that respects all of them.
- An order is impossible exactly when the rules form a cycle (A needs B, B needs C, C needs A).
- Up to 2,000 courses and 5,000 rules: repeating a full search for every course is wasteful, and trying orderings is hopeless.
Start with brute force
A course is stuck if following "is a prerequisite of" arrows leads back to itself. So for each course, walk everything that depends on it, and report failure if the walk comes back to the start.
def can_finish_brute(n, prerequisites):
nxt = defaultdict(list)
for course, need in prerequisites:
nxt[need].append(course)
for start in range(n):
seen, st = set(), list(nxt[start])
while st:
x = st.pop()
if x == start:
return False
if x not in seen:
seen.add(x)
st.extend(nxt[x])
return True
Each of the n starts may walk the whole graph, so time is O(V·(V + E)). With V = 2,000 and E = 5,000 that is about 1.4 × 10^7 steps, which is fine here, but with 10^5 courses and rules it would be about 10^10. Space is O(V + E).
From brute force to the idea
- Find the waste. The brute force re-walks the same parts of the graph from each start, only to ask one yes/no question.
- Think like a student. A course with no unmet prerequisites can be taken right now. Taking it may free others.
- Count unmet prerequisites.
indeg[c]is the number of prerequisites of c.nxt[need]lists the courses that wait forneed. - Peel off the free courses. Queue every course with
indeg == 0. When you take one, reduceindegof each course that was waiting for it, and queue any that reaches 0. This is Kahn's algorithm. - Count what you took. Courses on a cycle wait for each other and never reach 0, so they are never taken. If
len(taken) == n, there is no cycle.
The key idea: repeatedly take what is free, and a cycle shows up as courses that never become free.
The key idea
Kahn’s topological sort: count incoming arrows, repeatedly take courses with count 0. All taken ⇔ no cycle.
Python solution
def can_finish(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 len(taken) == nLeetCode 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)): a walk from every course | O(V + E): the adjacency lists and a seen 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 taken |
Edge cases
- No prerequisites (
n = 3,[]): returnsTrue. - A course that needs itself (
[[0, 0]]): returnsFalse, since it never reaches 0. - A two-course loop (
[[0,1],[1,0]]): returnsFalse. - A loop plus free courses (
n = 3,[[1,0],[1,2],[2,1]]): course 0 is taken but 1 and 2 are not, so the result isFalse. - Duplicate rules (
[[1,0],[1,0]]): counted twice inindegand decremented twice, so the result isTrue. n = 0: returnsTrue. The shown code needsdequeanddefaultdictimported.
Common mistakes
- Reversing the edge direction (
nxt[course]instead ofnxt[need]) so the in-degrees and the arrows disagree. - Returning after the first course with
indeg == 0without checking that all n were taken. - Treating the rules as undirected, which cannot tell a real loop from two courses linked in one direction.
- Forgetting courses that never appear in any rule, which still count towards n.
- Using recursion for a deep chain of 2,000 courses without checking the recursion limit.
You can take any number of courses per semester, but only those whose prerequisites were taken in an earlier semester. Return the minimum number of semesters to finish all courses, or -1 if impossible. Describe what changes, then write it if you like.
Compare with our answer
Run Kahn's algorithm level by level. Each level is the set of courses that are free at the same moment, so it is one semester.
def min_semesters(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, semesters = 0, 0
while q:
semesters += 1
for _ in range(len(q)):
c = q.popleft()
taken += 1
for d in nxt[c]:
indeg[d] -= 1
if indeg[d] == 0:
q.append(d)
return semesters if taken == n else -1
Time O(V + E), space O(V + E). The answer is the length of the longest prerequisite chain.
A strong answer mentions: processing the queue in levels, counting a level as a semester, and returning -1 when not all courses were taken.
1. A build tool reads rules such as "module A must be built before module B" for thousands of modules. It must report whether the rules can be satisfied. Which approach fits best?
Satisfiable rules mean the directed graph has no cycle, which a topological sort detects. Union-find ignores direction, BFS reachability does not test for cycles, and alphabetical order is unrelated to the rules.
2. Why does len(taken) == n tell you that the courses can all be finished?
Courses in a loop keep waiting for each other, so they are never queued. If nothing is missing, there is no loop. A course needs all its prerequisites taken, not just the first.
3. A learner changes the last line to return len(taken) > 0. Which input now returns a wrong answer?
In the last input course 0 is free and gets taken, so taken is not empty, yet courses 1 and 2 form a loop and the answer should be False. In the third input nothing is taken, so both versions return False.
Score 60% or more and the lesson is marked complete.