Course Schedule

MediumTopological Sort · Cycle Detection🧩 Topological Sort LeetCode #207 ↗Updated Oct 30, 2026

Problem

There are numCourses courses labelled 0 to numCourses - 1. Each pair [a, b] in prerequisites says course b must be completed before course a. Return true if some ordering lets you finish every course, otherwise false.

InputnumCourses = 2, prerequisites = [[1,0]]Outputtrue

InputnumCourses = 2, prerequisites = [[1,0],[0,1]]Outputfalse

InputnumCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]Outputtrue

1 ≤ numCourses ≤ 2000 · 0 ≤ prerequisites.length ≤ 5000 · all pairs are distinct

Try it yourself

Java

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Draw an edge b → a for each prerequisite. All courses can be taken exactly when this directed graph has no cycle — i.e. a topological order exists.

PatternTopological Sort

Instinct Tasks with prerequisites, "X must come before Y", or an order hidden in comparisons: build a directed graph and peel off nodes with zero in-degree.

Memory hack No prereqs? Off you go. Each finished task frees its followers; if someone is never freed, there is a cycle.

Open the Topological Sort guide →

Approaches

Brute ForceSearch for a Cycle from Every Course

Time O(V·(V+E))Space O(V+E)

For each course s, run a fresh graph search along prerequisite edges. If the search ever walks back into s, then s lies on a cycle and is impossible. If no course reaches itself, the graph is acyclic.

Java

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> next = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) next.add(new ArrayList<>());
    for (int[] p : prerequisites) next.get(p[1]).add(p[0]);
    for (int start = 0; start < numCourses; start++) {
        boolean[] seen = new boolean[numCourses];
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int cur = stack.pop();
            for (int nxt : next.get(cur)) {
                if (nxt == start) return false;    // came back around: cycle
                if (!seen[nxt]) {
                    seen[nxt] = true;
                    stack.push(nxt);
                }
            }
        }
    }
    return true;
}

Easy to justify, but repeats a full traversal for every course.

BetterDFS with Three Colours

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

Mark nodes white (unvisited), grey (on the current DFS path) or black (fully explored, known safe). Meeting a grey node means a back edge, i.e. a cycle. Black nodes are never re-explored, so one pass over the graph suffices.

Java

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> next = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) next.add(new ArrayList<>());
    for (int[] p : prerequisites) next.get(p[1]).add(p[0]);
    int[] color = new int[numCourses];            // 0 white, 1 grey, 2 black
    for (int i = 0; i < numCourses; i++) {
        if (color[i] == 0 && hasCycle(i, next, color)) return false;
    }
    return true;
}

private boolean hasCycle(int u, List<List<Integer>> next, int[] color) {
    color[u] = 1;
    for (int v : next.get(u)) {
        if (color[v] == 1) return true;            // back edge to the current path
        if (color[v] == 0 && hasCycle(v, next, color)) return true;
    }
    color[u] = 2;
    return false;
}

Linear, but recursion depth can reach V on a long chain.

OptimalKahn’s Algorithm (BFS Peeling)

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

Count in-degrees (unmet prerequisites). Queue every course with none, “take” it, and decrement its dependents; any that reach 0 join the queue. Courses on a cycle never reach in-degree 0, so all are finishable iff every course gets taken.

Java

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> next = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) next.add(new ArrayList<>());
    int[] indegree = new int[numCourses];
    for (int[] p : prerequisites) {
        next.get(p[1]).add(p[0]);
        indegree[p[0]]++;
    }
    Deque<Integer> queue = new ArrayDeque<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    int taken = 0;
    while (!queue.isEmpty()) {
        int c = queue.poll();
        taken++;
        for (int d : next.get(c)) {
            if (--indegree[d] == 0) queue.offer(d);
        }
    }
    return taken == numCourses;                    // leftovers are stuck on a cycle
}

Linear and iterative — no recursion, and it yields an actual course order.

Pro tip

Keep the dequeued courses in a list and you have solved Course Schedule II for free.

At a glance

Level	Approach	Time	Space
Brute Force	Search for a Cycle from Every Course	`O(V·(V+E))`	`O(V+E)`
Better	DFS with Three Colours	`O(V+E)`	`O(V+E)`
Optimal	Kahn’s Algorithm (BFS Peeling)	`O(V+E)`	`O(V+E)`

Common pitfalls

Reversing the edge direction for [a, b] — harmless here, fatal in Course Schedule II.
Using a single visited flag in DFS — it cannot tell a back edge from a cross edge.
Forgetting isolated courses — start DFS / seed the queue from every node.

Interview tips

Translate immediately: “can finish all” = “dependency graph is a DAG”.
Know both DFS colouring and Kahn’s; pick Kahn’s if recursion depth is a concern.
Mention the follow-up (return the order) and how each method produces it.

Pattern

Topological sort / cycle detection → tasks with “X before Y” dependencies and a feasibility or ordering question.

My notes saved in this browser