Course Schedule

Share

There are numCourses courses labeled 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses, otherwise return false.

Essentially: can all courses be completed? This is equivalent to asking whether the prerequisite dependency graph has no cycles.

Example 1
Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: Course 0 → Course 1. No cycle. Possible.
Example 2
Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: 0 requires 1 and 1 requires 0. Cycle, impossible.
Constraints:

Contents

Solution 1: Kahn's Algorithm (BFS)

Build the graph from prerequisites. Run topological sort. If we can process all numCourses nodes, no cycle exists → return true.

Java
public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    int[] indegree = new int[numCourses];

    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());

    for (int[] pre : prerequisites) {
        int course = pre[0], prereq = pre[1];
        adj.get(prereq).add(course); // prereq → course
        indegree[course]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) queue.offer(i); // no prerequisites
    }

    int processed = 0;
    while (!queue.isEmpty()) {
        int course = queue.poll();
        processed++;
        for (int next : adj.get(course)) {
            indegree[next]--;
            if (indegree[next] == 0) queue.offer(next);
        }
    }

    return processed == numCourses; // true if all courses were processable
}

Solution 2: DFS with 3-Color Marking

Use three states for each node:

If during DFS we encounter a node with state 1, we've found a cycle.

Java
public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());

    for (int[] pre : prerequisites) {
        adj.get(pre[1]).add(pre[0]);
    }

    int[] state = new int[numCourses]; // 0=unvisited, 1=visiting, 2=done

    for (int i = 0; i < numCourses; i++) {
        if (state[i] == 0 && hasCycle(i, adj, state)) return false;
    }
    return true;
}

private boolean hasCycle(int node, List<List<Integer>> adj, int[] state) {
    state[node] = 1; // mark as visiting

    for (int neighbor : adj.get(node)) {
        if (state[neighbor] == 1) return true;  // back edge → cycle
        if (state[neighbor] == 0 && hasCycle(neighbor, adj, state)) return true;
    }

    state[node] = 2; // mark as fully processed
    return false;
}

Complexity Analysis