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 start course a. Return true if some order lets you finish every course, and false if none does.
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, which frees 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, 2 waits for 1, and 1 waits for 0. The three wait for each other in a loop, so none of them can go first.
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 fewest terms that cover 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
Draw an arrow b → a for each pair [a, b]. Every course can be finished exactly when this graph, with V = numCourses nodes and E = prerequisites.length arrows, has no cycle. Kahn's algorithm checks it the way a student plans: keep taking a course whose prerequisites are done, and see whether every course gets taken.
Take every free course, round after round
Correct, but does not finish on the largest tests
Intuition
In each round, take every untaken course whose prerequisites are all taken. Stop when a round takes nothing, and answer true if every course was taken. A round takes nothing only when every leftover course waits for another leftover course, which is a cycle.
Each round rereads every pair and every course, yet may take a single course. A chain of 5,001 courses among 100,000 needs over 5,000 rounds: about 5 × 10^8 checks.
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
Depth first search finds a cycle by tracking the path it is walking. Give each course one of three states: not visited, on the path, done. Follow arrows from a course to the courses that wait for it. Mark a course on the path when you enter it, and done when all its arrows are explored.
An arrow to a course on the path closes a loop: return false. An arrow to a done course is safe, because everything reachable from it was checked and holds no cycle, so a course reached twice is not by itself a cycle. Each course is entered once and each arrow followed once: O(V + E).
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
A course becomes free at one moment: when its last prerequisite is taken. So keep each course's in-degree, the number of prerequisites it still waits for, and start a queue with every course whose count is 0. Taking a course lowers the count of each course that waits for it, and a count that reaches 0 joins the queue. In the first example the counts start at 0, 1, 1, 1: taking 0 frees 1, and taking 1 frees 2 and 3. Each course enters the queue once and each pair lowers one count once: O(V + E).
If the queue empties while course a is untaken, its count is above 0, so a prerequisite of a is untaken too, and so on. That walk must revisit a course: a cycle. Conversely, each course on a cycle waits for another one on it, so none goes first. The order courses leave 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
- Mixing up the direction.
[a, b]means b comes first: the arrow runs from b to a, and the in-degree of a goes up. - Forgetting courses that appear in no pair. With
numCourses = 5and the single pair[4, 3], courses 0, 1 and 2 must start in the queue too. - 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 and looks like a cycle if you only track "seen".
- Recursing on a chain of 5,000 courses: 5,000 calls deep, past Python's default limit of 1,000.
- Returning true when the queue empties without checking that
numCoursescourses were taken. The second example would return true.
Frequently asked questions3
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. Every pair is read once, and every course is handled once. The lists and counts take O(V + E) space.
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 gives you a valid order of courses. Depth first search with three states 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 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 such an order exists.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def canFinish(numCourses, prerequisites):
# Write code hereTest #1
Test #2
Arguments
numCourses = 4 prerequisites = [[1, 0], [2, 1], [3, 1]]
Expected Output
true