Course Schedule
There are numCourses courses, numbered 0 to numCourses-1. Each pair [a, b] in prerequisites means you have to finish course b before you can start course a. Return true if there is an order in which you can finish every course, and false if there is none.
Function
- numCoursesinteger
- the number of courses
- prerequisitesinteger-2d-array
- the pairs [a, b], each meaning course b comes before course a
- Returnsboolean
- true if every course can be finished, false otherwise
Constraints
1 ≤ numCourses ≤ 1051 ≤ prerequisites.length ≤ 5000- Each pair
[a, b]has0 ≤ a, b < numCourses. - No pair appears twice.
- A pair may name the same course twice,
[a, a]. That course needs itself first, so it can never be taken.
Examples
- Input
- numCourses = 4prerequisites = [[1, 0], [2, 1], [3, 1]]
- Output
- true
- Explanation
- Course 0 has no prerequisites, so you take it first. That frees course 1, and course 1 frees both 2 and 3, so the order 0, 1, 2, 3 works.
- Input
- numCourses = 3prerequisites = [[0, 2], [2, 1], [1, 0]]
- Output
- false
- Explanation
- Course 0 waits for 2, course 2 waits for 1, and course 1 waits for 0. The three wait for each other in a loop, so none of them can be the first one you take.
+20 hidden tests on Submit
Follow-up
Any number of courses fit in one term, as long as each course's prerequisites were finished in earlier terms. What is the smallest number of terms that covers every course?
Hints
Open them one at a time. Each one gives away a little more.
Draw each course as a dot and each pair
[a, b]as an arrow frombtoa. What shape in that drawing would make it impossible to finish?A loop of arrows. Every course on a loop waits for another course of the same loop, so none of them can ever go first. The question is whether the graph has a cycle.
Count how many prerequisites each course still waits for. Start a queue with the courses whose count is 0, and each time you take one, lower the count of every course that waits for it. If fewer than
numCoursescourses ever reach the queue, there is a cycle.
Solution
Turn the pairs into a directed graph with V = numCourses nodes and E = prerequisites.length edges, one arrow b → a for each pair [a, b]. Every course can be finished exactly when that graph has no cycle. Kahn's algorithm decides it the way a student would plan: keep taking a course whose prerequisites are all done, and see whether you run out of courses or run out of options first.
Take every free course, round after round
Correct, but does not finish on the largest tests
Intuition
Plan the way a student would. In each round, look at every course you have not taken. If all of its prerequisites are taken, take it. Repeat until a round takes nothing. If every course is taken by then, the answer is true.
Why a stuck round means false: when a round takes nothing, every course left has a prerequisite that is also left. Start at any leftover course and keep stepping to one of its untaken prerequisites. You never run out of steps, and there are only so many courses, so you come back to a course you already visited. That is a cycle, and the courses on it wait for each other forever.
The method is correct, but every round rereads every pair and every course, and a round can take as few as one course. A chain of 5,001 courses, each needing the one before it, takes over 5,000 rounds; among 100,000 courses that is about 5 × 10^8 checks, almost all of them on courses whose status did not change.
Algorithm
- Mark every course as not taken.
- Mark a course blocked if some pair gives it a prerequisite that is not taken.
- Take every course that is neither taken nor blocked.
- If the round took nothing, stop; otherwise go back to step 2.
- Return true if every course is taken.
def canFinish(numCourses, prerequisites):
taken = [False] * numCourses
count = 0
while True:
# A course is blocked while one of its prerequisites is not taken.
blocked = [False] * numCourses
for course, before in prerequisites:
if not taken[before]:
blocked[course] = True
# Take every course that is free this round.
progress = False
for c in range(numCourses):
if not taken[c] and not blocked[c]:
taken[c] = True
count += 1
progress = True
if not progress:
break
return count == numCoursesDepth first search with three states
Intuition
A cycle is a path that comes back to where it started. Depth first search finds one by remembering which courses are on the path it is walking right now. Give every course one of three states: not visited, on the current path, and done.
Walk from a course along its arrows to the courses that wait for it. Mark a course "on the path" when you step onto it, and "done" when every arrow out of it is explored and you step back. An arrow to a course that is on the path means you walked in a circle: return false. An arrow to a done course is safe, since everything reachable from it was checked and holds no cycle, so you skip it. Each course is entered once and each arrow is followed once.
Two states are not enough. In the diamond 0 → 1, 0 → 2, 1 → 3, 2 → 3 the search reaches course 3 a second time through 2, but 3 is done by then, not on the path, and there is no cycle. Only an arrow back into the current path closes a loop.
Write the search with your own stack and, per course, the position of its next unexplored arrow. The recursive version is shorter, but a chain of 5,000 courses would go 5,000 calls deep.
Algorithm
- Build, for every course, the list of courses that wait for it.
- For each course that is not visited, mark it on the path and push it on a stack.
- Look at the top of the stack. If it has no arrow left, mark it done and pop it; otherwise follow its next arrow.
- If the arrow leads to a course on the path, return false. If it leads to a course not visited, mark that course on the path and push it.
- When every course is done, return true.
def canFinish(numCourses, prerequisites):
unlocks = [[] for _ in range(numCourses)]
for course, before in prerequisites:
unlocks[before].append(course)
# 0 = not visited, 1 = on the current path, 2 = done, no cycle below it
state = [0] * numCourses
# next_edge[c] counts the edges out of c the search has already followed.
next_edge = [0] * numCourses
for start in range(numCourses):
if state[start] != 0:
continue
# A stack of our own instead of recursion: a chain of 5,000
# courses would go 5,000 calls deep.
state[start] = 1
stack = [start]
while stack:
course = stack[-1]
if next_edge[course] == len(unlocks[course]):
state[course] = 2
stack.pop()
continue
nxt = unlocks[course][next_edge[course]]
next_edge[course] += 1
if state[nxt] == 1:
return False # an edge back to the current path closes a cycle
if state[nxt] == 0:
state[nxt] = 1
stack.append(nxt)
return TrueKahn's algorithm
Intuition
The rounds in the first approach waste their time rechecking courses that did not change. A course becomes free at one moment only: when its last prerequisite is taken. So count, for every course, how many prerequisites it still waits for, its in-degree. When you take a course, lower the count of every course that waits for it. A count that drops to 0 means that course is free right now, so you put it in a queue.
Start the queue with every course whose count is 0 from the beginning, then take courses from the queue until it is empty. In the first example the counts start at 0, 1, 1, 1 for courses 0 to 3. Taking 0 drops course 1 to 0; taking 1 drops courses 2 and 3 to 0; all four are taken, so the answer is true. Each course enters the queue at most once and each pair lowers one count once, so the work is O(V + E).
Why a leftover course means a cycle: if the queue empties while course a is not taken, its count is above 0, so one of its prerequisites, b, was never taken either. The same holds for b, and so on. A walk from course to untaken prerequisite never stops, so it revisits a course, which is a cycle. In the second example no count starts at 0, the queue starts empty, and none of the three courses is taken.
The other direction holds too: a course on a cycle waits for another course of the same cycle, so its count cannot reach 0 before that one is taken, and none of them ever goes first. So "every course taken" and "no cycle" are the same statement. As a bonus, the order in which courses left the queue is a valid schedule.
Algorithm
- For each pair [a, b], add a to the list of courses that wait for b, and add 1 to the in-degree of a.
- Put every course with in-degree 0 in a queue.
- Take a course from the queue and count it. Lower the in-degree of every course that waits for it, and add each one that reaches 0 to the queue.
- When the queue is empty, return whether the count equals
numCourses.
from collections import deque
def canFinish(numCourses, prerequisites):
# unlocks[b] lists the courses that wait for b.
# indegree[a] counts the prerequisites of a that are not taken yet.
unlocks = [[] for _ in range(numCourses)]
indegree = [0] * numCourses
for course, before in prerequisites:
unlocks[before].append(course)
indegree[course] += 1
# Every course with no prerequisites can be taken right away.
queue = deque(c for c in range(numCourses) if indegree[c] == 0)
taken = 0
while queue:
course = queue.popleft()
taken += 1
for nxt in unlocks[course]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
queue.append(nxt)
# A course on a cycle never gets down to 0, so it is never taken.
return taken == numCourses
Pitfalls and edge cases
Most bugs come from the direction of a pair, from a cycle check that is too strict, or from courses that appear in no pair.
- Mixing up the direction.
[a, b]means b comes first, so the arrow runs from b to a and the in-degree of a goes up. Building the lists one way and counting in-degrees the other way breaks the algorithm. - Forgetting courses that appear in no pair. With
numCourses = 5and the single pair[4, 3], courses 0, 1 and 2 still count. Start the queue with every course whose in-degree is 0, not only the ones you saw in a pair. - A course that is its own prerequisite,
[2, 2]. It is a cycle of length one: its in-degree never reaches 0 and the answer is false. - Two states instead of three in the depth first search. In the diamond 0 → 1, 0 → 2, 1 → 3, 2 → 3, course 3 is reached twice, which looks like a cycle if you only track "seen". Only an arrow back into the current path closes a loop.
- Recursion on long chains. A chain of 5,000 courses goes 5,000 calls deep, past Python's default limit of 1,000.
- Returning true when the queue empties without comparing the number of courses taken with
numCourses.
Frequently asked questions4
What is the time complexity of the Course Schedule problem?
O(V + E), where V is the number of courses and E the number of pairs, with either Kahn's algorithm or depth first search. Building the lists reads every pair once, every course enters the queue at most once, and every pair lowers one count once. The lists and counts take O(V + E) space.
Why does a course left over in Kahn's algorithm mean there is a cycle?
A course is left over only if its count never reached 0, so at least one of its prerequisites is left over too. Follow that wait from course to course: every step lands on another leftover course, and with finitely many courses the walk must come back to one it has seen. The stretch between the two visits is a cycle.
Should you use BFS or DFS for Course Schedule?
Both run in O(V + E). Kahn's algorithm, the breadth first version, has no recursion depth to worry about and hands you a valid order of courses for free. Depth first search with three states is as fast and is the natural choice when you also have to report the cycle, because the courses on its stack form it.
What is a topological sort?
An order of the nodes of a directed graph in which every arrow points forward; here, an order of courses in which every prerequisite comes before the course that needs it. It exists exactly when the graph has no cycle, and the order in which Kahn's algorithm takes courses is one. Course Schedule asks whether a topological order exists.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def canFinish(numCourses, prerequisites):
# Write code hereCase 1
Case 2
Input
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Expected
true