MediumNo. 0207

Course Schedule — LeetCode 207 Python Solution

Topics
Depth-First Search, Breadth-First Search, Graph, Topological Sort
Reading time
3 min

The problem

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

Example

Input
numCourses = 2, prerequisites = [[1,0]]
Output
true
Explanation
There are a total of 2 courses to take.

Python solution

PythonSolution
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        g = [[] for _ in range(numCourses)]
        indeg = [0] * numCourses
        for a, b in prerequisites:
            g[b].append(a)
            indeg[a] += 1
        q = [i for i, x in enumerate(indeg) if x == 0]
        for i in q:
            numCourses -= 1
            for j in g[i]:
                indeg[j] -= 1
                if indeg[j] == 0:
                    q.append(j)
        return numCourses == 0

Complexity

Time
O(n + m)
Space · auxiliary
O(n + m)

Pattern: Topological Sort

Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 207. Course Schedule is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.

The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 207. Course Schedule?

LeetCode 207. Course Schedule is rated Medium on LeetCode.

What is the time complexity of LeetCode 207. Course Schedule?

The Python solution on this page runs in O(n + m).

What is the space complexity of LeetCode 207. Course Schedule?

The Python solution on this page uses O(n + m) auxiliary space.

What topics does LeetCode 207. Course Schedule cover?

LeetCode 207. Course Schedule is tagged Depth-First Search, Breadth-First Search, Graph and Topological Sort on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.