Course Schedule

There are n courses, numbered 0 to n - 1. Each prerequisite [a, b] means course b must be taken before course a. Return true if it's possible to finish every course.

LeetCode: 207. Course Schedule

Example

Text

n = 4, prerequisites = [[1, 0], [2, 0], [3, 1], [3, 2]]
Output: true   (for example 0, 1, 2, 3)

n = 2, prerequisites = [[1, 0], [0, 1]]
Output: false  (each course needs the other first)

graph LR
    0 --> 1
    0 --> 2
    1 --> 3
    2 --> 3

Courses are vertices, and each prerequisite [a, b] is an edge b → a. All courses can be finished exactly when this directed graph has no cycle: that's the question answered in Detect a Cycle in a Directed Graph. This article solves it in the terms of the problem and also returns a valid order (LeetCode 210).

Brute force: repeatedly take a ready course

A course is ready when all its prerequisites have been taken. Scan all the courses for one that's ready, take it, and repeat. If a full scan finds nothing ready while courses remain, they're blocked by a cycle.

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Main {
    // Returns null when a cycle blocks some courses.
    static List<Integer> findOrder(int n, int[][] prerequisites) {
        boolean[] taken = new boolean[n];
        List<Integer> order = new ArrayList<>();
        while (order.size() < n) {
            int ready = -1;
            for (int course = 0; course < n && ready == -1; course++) {
                if (taken[course]) continue;
                boolean allTaken = true;
                for (int[] p : prerequisites) {
                    if (p[0] == course && !taken[p[1]]) {
                        allTaken = false;
                        break;
                    }
                }
                if (allTaken) ready = course;
            }
            if (ready == -1) return null; // nothing ready: a cycle blocks the rest
            taken[ready] = true;
            order.add(ready);
        }
        return order;
    }

    static boolean canFinish(int n, int[][] prerequisites) {
        return findOrder(n, prerequisites) != null;
    }

    public static void main(String[] args) {
        int[][] prereqs = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        System.out.println(canFinish(4, prereqs) + " " + findOrder(4, prereqs));
        System.out.println(canFinish(2, new int[][]{{1, 0}, {0, 1}}));
    }
}

Output

true [0, 1, 2, 3]
false

Time: O(n² · E) for E prerequisites: up to n rounds, each checking every course against every prerequisite. Space: O(n).

The method returns null instead of a list when no order exists. null is the Java value for "no object".

Optimal: Kahn's algorithm

Instead of rescanning for ready courses, keep track of how many prerequisites each course is still waiting for (its in-degree), and keep the ready courses in a queue (ArrayDeque is Java's array-backed double-ended queue):

Build an adjacency list b → a and count each course's in-degree.
Queue every course with in-degree 0.
Take a course from the queue and add it to the order. Each course that depends on it has one fewer prerequisite left; queue those that reach 0.

If the order ends up with all n courses, they can all be finished, and the order is a valid schedule.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;

public class Main {
    static List<Integer> findOrder(int n, int[][] prerequisites) {
        List<List<Integer>> unlocks = new ArrayList<>();
        for (int i = 0; i < n; i++) unlocks.add(new ArrayList<>());
        int[] waiting = new int[n];
        for (int[] p : prerequisites) {
            unlocks.get(p[1]).add(p[0]);
            waiting[p[0]]++;
        }
        Queue<Integer> ready = new ArrayDeque<>();
        for (int c = 0; c < n; c++) {
            if (waiting[c] == 0) ready.add(c);
        }
        List<Integer> order = new ArrayList<>();
        while (!ready.isEmpty()) {
            int course = ready.poll();
            order.add(course);
            for (int next : unlocks.get(course)) {
                waiting[next]--;
                if (waiting[next] == 0) ready.add(next);
            }
        }
        return order.size() == n ? order : null;
    }

    static boolean canFinish(int n, int[][] prerequisites) {
        return findOrder(n, prerequisites) != null;
    }

    public static void main(String[] args) {
        int[][] prereqs = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        System.out.println(canFinish(4, prereqs) + " " + findOrder(4, prereqs));
        System.out.println(canFinish(2, new int[][]{{1, 0}, {0, 1}}));
        System.out.println(findOrder(3, new int[0][]) + " " + canFinish(3, new int[][]{{0, 1}, {1, 2}, {2, 1}}));
    }
}

Output

true [0, 1, 2, 3]
false
[0, 1, 2] false

Time: O(n + E): every course is queued once, and every prerequisite is followed once. Space: O(n + E) for the adjacency list.

Courses on a cycle never reach in-degree 0, so they never enter the queue, and order comes up short. A DFS with three vertex states, as in Detect a Cycle in a Directed Graph, gives the same answer, and reversing its finishing order gives a valid schedule too.

Edge cases

No prerequisites: every course is ready; any order works.
A course that requires itself ([a, a]): a self-loop, so it can never be taken.
Duplicate prerequisites: counted twice in waiting and removed twice in unlocks, so the result is still correct.