What are the common mistakes?

- Reversing the edge direction: [a, b] means b comes before a, so the edge goes from b to a. - Forgetting courses that appear in no prerequisite pair. They start with in-degree 0 and must be in the initial queue. - Using a recursive DFS without tracking the "currently visiting" state, which misses cycles or overflows the stack on deep graphs.

DSA patterns

Course Schedule

mediumGraphs Must-do

There are n courses labelled 0 to n - 1, and a list of prerequisite pairs [a, b] meaning you must take course b before course a. Decide whether it's possible to finish every course.

Examples

Example 1

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

Output: False

Explanation: Course 1 needs course 0 and course 0 needs course 1, a circular dependency.

Approach

Optimal

Courses and prerequisites form a directed graph. You can finish everything exactly when the graph has no cycle. Kahn's algorithm finds out: repeatedly take any course with no remaining prerequisites, "complete" it, and remove it as a prerequisite from the others. If you can complete all n courses this way, there's no cycle.

Build an adjacency list (prerequisite -> courses that depend on it) and count each course's unmet prerequisites (its in-degree).
Put every course with in-degree 0 into a queue: they can be taken right away.
Pop a course, count it as completed, and decrease the in-degree of every course that depends on it. Any course that reaches 0 joins the queue.
When the queue empties, all courses are finishable only if the completed count equals n. Anything left over is stuck in a cycle.

ComplexityTime O(V + E)Space O(V + E)

Python

from collections import deque
 
def can_finish(num_courses: int, prerequisites: list[list[int]]) -> bool:
    dependents = [[] for _ in range(num_courses)]
    indegree = [0] * num_courses
    for course, prereq in prerequisites:
        dependents[prereq].append(course)
        indegree[course] += 1
 
    ready = deque(c for c in range(num_courses) if indegree[c] == 0)
    completed = 0
    while ready:
        course = ready.popleft()
        completed += 1
        for nxt in dependents[course]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                ready.append(nxt)
    return completed == num_courses

Frequently asked questions

Swap "courses" for "resources" and this is how Terraform decides the order to create infrastructure, how Kubernetes operators and init systems order dependent services, and how CI pipelines schedule jobs that depend on other jobs. "Detect a circular dependency" is a classic Platform and SRE interview question, and the follow-up, Course Schedule II, asks you to return the actual order.

Reversing the edge direction: [a, b] means b comes before a, so the edge goes from b to a.
Forgetting courses that appear in no prerequisite pair. They start with in-degree 0 and must be in the initial queue.
Using a recursive DFS without tracking the "currently visiting" state, which misses cycles or overflows the stack on deep graphs.