Problem statement

There are numCourses courses labelled 0..numCourses-1. prerequisites[i] = [a, b] means you must take course b before course a.

Return true if you can finish all courses (i.e. the prerequisite graph has no cycle).

Example 1

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

Example 2

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 0 and 1 require each other.

Constraints

• 1 <= numCourses <= 10
• 0 <= prerequisites.length <= 20

Hints for Course Schedule

1. Hint 1

   This is cycle detection in a directed graph.

2. Hint 2

   Kahn's algorithm: repeatedly remove nodes with in-degree 0; a leftover node means a cycle.

How to solve Course Schedule

You can finish every course exactly when the prerequisite graph has no cycle — a cycle is a set of courses each waiting on another, so none can ever be taken first. Kahn's algorithm detects that by repeatedly removing courses with nothing left to wait for; whatever cannot be removed is trapped in a cycle.

Approach

1. Build the graph with an edge b -> a for each pair [a, b] (b must come first), and count each course's in-degree.
2. Seed a queue with every course of in-degree 0 — those have no unmet prerequisites.
3. Pop a course, count it as taken, and decrement the in-degree of each course depending on it.
4. Any course whose in-degree drops to 0 becomes available; push it.
5. If the number taken equals numCourses, everything was schedulable — otherwise a cycle blocked the rest.

Why it works

A course leaves the queue only once all of its prerequisites have already left, so the pop order is a valid schedule. If the graph is acyclic, every course eventually reaches in-degree 0 — a directed acyclic graph always has a source — so all are taken. If a cycle exists, none of its members ever reaches in-degree 0, since each is waiting on another member, so the count falls short. The comparison is therefore an exact cycle test.

Complexity

• Time — O(V + E)
• Space — O(V + E)

Pitfalls

• Mind the edge direction: [a, b] means b comes before a, so the edge runs b -> a and it is a's in-degree that grows.
• Compare the count taken against numCourses, not against the number of edges.
• Courses with no prerequisites at all must still be seeded into the queue.
• Duplicate prerequisite pairs are fine as long as in-degree and adjacency stay consistent — count the duplicate in both.

Reference solution

Python

from typing import List
from collections import deque

def canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool:
    indeg = [0] * numCourses
    adj = [[] for _ in range(numCourses)]
    for a, b in prerequisites:
        adj[b].append(a)
        indeg[a] += 1
    queue = deque(i for i in range(numCourses) if indeg[i] == 0)
    taken = 0
    while queue:
        c = queue.popleft()
        taken += 1
        for nxt in adj[c]:
            indeg[nxt] -= 1
            if indeg[nxt] == 0:
                queue.append(nxt)
    return taken == numCourses

Java

public static boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    int[] indeg = new int[numCourses];
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<Integer>());
    for (int[] p : prerequisites) {
        adj.get(p[1]).add(p[0]);
        indeg[p[0]]++;
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) queue.add(i);
    int done = 0;
    while (!queue.isEmpty()) {
        int u = queue.poll();
        done++;
        for (int v : adj.get(u)) {
            indeg[v]--;
            if (indeg[v] == 0) queue.add(v);
        }
    }
    return done == numCourses;
}

C++

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(numCourses);
    vector<int> indeg(numCourses, 0);
    for (const auto& p : prerequisites) {
        adj[p[1]].push_back(p[0]);
        indeg[p[0]]++;
    }
    vector<int> queue;
    for (int i = 0; i < numCourses; i++) if (indeg[i] == 0) queue.push_back(i);
    int done = 0;
    size_t head = 0;
    while (head < queue.size()) {
        int u = queue[head++];
        done++;
        for (int v : adj[u]) {
            indeg[v]--;
            if (indeg[v] == 0) queue.push_back(v);
        }
    }
    return done == numCourses;
}

JavaScript

var canFinish = function(numCourses, prerequisites) {
    const indeg = new Array(numCourses).fill(0);
    const adj = [];
    for (let i = 0; i < numCourses; i++) adj.push([]);
    for (const p of prerequisites) {
        adj[p[1]].push(p[0]);
        indeg[p[0]]++;
    }
    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indeg[i] === 0) queue.push(i);
    }
    let taken = 0;
    let head = 0;
    while (head < queue.length) {
        const c = queue[head++];
        taken++;
        for (const nxt of adj[c]) {
            if (--indeg[nxt] === 0) queue.push(nxt);
        }
    }
    return taken === numCourses;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Minimize Maximum Component Cost Medium
• Minimum Time for K Connected Components Medium
• Power Grid Maintenance Medium
• Minimum Time to Reach Destination in Directed Graph Medium
• Unit Conversion I Medium
• Digit Operations to Make Two Integers Equal Medium