Course Schedule

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Constraints:

• 1 <= numCourses <= 2000
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• All the pairs prerequisites[i] are unique.

Approach: Topological Sort (Kahn’s Algorithm)

Algorithm

1. Model courses as nodes and prerequisites as directed edges: bi → ai
2. Build the adjacency list g and compute the in-degree of each course
3. Enqueue all courses with in-degree 0 — these have no prerequisites
4. While the queue is not empty:
   • Poll a course and decrement the remaining course count
   • For each dependent course, decrement its in-degree
   • If a dependent’s in-degree reaches 0, enqueue it
5. If all courses were processed (remaining == 0), no cycle exists; otherwise a cycle blocks completion

Key Insight

A valid schedule exists if and only if the prerequisite graph is acyclic. Kahn’s algorithm detects cycles: a course can only be “taken” once all its prerequisites are done, so every processed course needs all its incoming edges resolved. If a cycle exists, its nodes never reach in-degree zero, so fewer than numCourses courses get processed.

Time & Space Complexity

• Time Complexity: O(n + m) - each course and prerequisite is processed once, where n = numCourses and m = prerequisites.length
• Space Complexity: O(n + m) - the adjacency list plus in-degree array

Java Implementation

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

public class CourseSchedule {

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] graph = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        int[] indeg = new int[numCourses];
        for (int[] p : prerequisites) {
            int a = p[0], b = p[1];
            graph[b].add(a); // b must come before a
            indeg[a]++;
        }

        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < numCourses; i++) {
            if (indeg[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int i = queue.poll();
            numCourses--;
            for (int j : graph[i]) {
                if (--indeg[j] == 0) {
                    queue.offer(j);
                }
            }
        }
        return numCourses == 0;
    }
}

Example Walkthrough

For numCourses = 2, prerequisites = [[1,0],[0,1]]:

1. Graph: 0 → 1 and 1 → 0. in-degree of 0 is 1, in-degree of 1 is 1
2. No course has in-degree 0, so the queue is empty
3. numCourses stays 2, which is not 0 → return false (cycle)

For numCourses = 2, prerequisites = [[1,0]]:

1. Graph: 0 → 1. in-degree of 0 is 0, in-degree of 1 is 1
2. Enqueue course 0, process it → in-degree of 1 becomes 0, enqueue course 1
3. All 2 courses processed → return true

Alternative Approach: DFS with State Detection

public class CourseScheduleDfs {

    private List<Integer>[] graph;
    private int[] state; // 0 = unvisited, 1 = visiting, 2 = visited

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        graph = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] p : prerequisites) {
            graph[p[1]].add(p[0]);
        }
        state = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(i)) {
                return false;
            }
        }
        return true;
    }

    private boolean hasCycle(int i) {
        if (state[i] == 1) {
            return true; // found a back edge to a node on the current path
        }
        if (state[i] == 2) {
            return false;
        }
        state[i] = 1;
        for (int j : graph[i]) {
            if (hasCycle(j)) {
                return true;
            }
        }
        state[i] = 2;
        return false;
    }
}

The DFS approach colors nodes as unvisited/visiting/visited. A back edge to a node currently being visited reveals a cycle. Both approaches run in O(n + m) time.

Key Insights

1. Cycle Detection: The core question reduces to whether the directed graph has a cycle
2. Kahn’s Algorithm: Counting processed nodes tells you directly if a full order exists
3. Edge Direction: bi → ai means the prerequisite points to the dependent course
4. In-degree Zero: Courses with in-degree zero have all prerequisites satisfied and are schedulable

Kahn’s topological sort is the optimal solution, providing O(n + m) time and O(n + m) space.