MediumDepth-First SearchBreadth-First SearchGraphTopological Sort

Course Schedule

1 approach, code in every language

You are given an integer numCourses representing the number of courses labeled from 0 to numCourses - 1. You are also given a list prerequisites where each entry [a, b] means you must complete course b before you are allowed to take course a.

Decide whether it is possible to finish every course. Return true if a valid order of study exists, and false otherwise.

The answer is false exactly when the prerequisite relationships form a cycle, because a cycle would force a course to depend on itself either directly or indirectly.

Example 1

Input: numCourses = 2, prerequisites = [[1,0]]

Output: true

There are two courses. Course 1 depends on course 0, so the order 0 then 1 finishes everything.

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]

Output: false

Course 1 needs course 0 and course 0 needs course 1. This circular dependency makes both impossible.

Constraints

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
All the pairs prerequisites[i] are unique.

Kahn's Algorithm (BFS Topological Sort)

Build the dependency graph, track indegrees, and peel off zero-indegree nodes one at a time.

Loading animation…

Intuition

A course can be taken once every prerequisite is done, which means it can be scheduled only when nothing still points at it. We model each edge b -> a and record how many prerequisites (indegree) each course has. Courses with indegree zero have no blockers, so we start with them. Every time we finish a course we relax its outgoing edges, decreasing the indegree of the courses that depended on it, and any course that drops to zero becomes available next. If a cycle exists, the nodes inside it never reach indegree zero, so they can never be processed. Counting how many nodes we successfully processed tells us whether the whole graph was schedulable.

Algorithm walkthrough

1Create an adjacency list and an indegree array; for each pair [a, b] add an edge b -> a and increment indegree[a].
2Push every course whose indegree is 0 into a queue, since these have no outstanding prerequisites.
3Pop a course, count it as processed, and for each dependent course reduce its indegree by one.
4Whenever a dependent's indegree becomes 0, enqueue it because all of its prerequisites are now satisfied.
5After the queue empties, compare the processed count to numCourses.
6Return true when every course was processed; a smaller count means a cycle blocked some courses, so return false.

Implementation

from collections import deque
from typing import List

class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for _ in range(numCourses)]
        indegree = [0] * numCourses
        for course, prereq in prerequisites:
            graph[prereq].append(course)
            indegree[course] += 1

        queue = deque(i for i in range(numCourses) if indegree[i] == 0)
        processed = 0
        while queue:
            node = queue.popleft()
            processed += 1
            for nxt in graph[node]:
                indegree[nxt] -= 1
                if indegree[nxt] == 0:
                    queue.append(nxt)

        return processed == numCourses

Time

O(V + E)

Space

O(V + E)

V = numCourses and E = prerequisites.length; every node and edge is handled once.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Graphs

After the pattern

Now solve one you haven't seen.

Apprenticeship Skill Plan is our own problem on the technique behind Course Schedule: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free