Skip to content
AI360Xpert
Back to Graphs
Medium

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`.

Examples

Input:numCourses = 2, prerequisites = [[1,0]]
Output:true
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
Input:numCourses = 2, prerequisites = [[1,0],[0,1]]
Output:false
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.

Topological Sort (DFS Cycle Detection)

Approach

This problem is equivalent to detecting a cycle in a directed graph. If there is a cycle, we cannot complete the courses. We build an adjacency list representing the prerequisites. Then, we perform DFS on each course. To detect cycles, we maintain a `visited` set for the current DFS path. If we encounter a node that is already in the `visited` set during our traversal, a cycle exists. To optimize, once a node is fully verified (no cycles from it), we can mark it as safe (e.g., by emptying its prerequisites list) so we don't traverse it again.

Complexity Analysis

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

V is the number of courses, E is the number of prerequisites. We traverse each node and each edge at most once. Space complexity is O(V + E) for the adjacency list and O(V) for the visited sets and recursion stack.

Solution.java
class Solution {    public boolean canFinish(int numCourses, int[][] prerequisites) {        // Build adjacency list        List<List<Integer>> adj = new ArrayList<>();        for (int i = 0; i < numCourses; i++) {            adj.add(new ArrayList<>());        }        for (int[] pre : prerequisites) {            adj.get(pre[0]).add(pre[1]);        }                // Track visited nodes in the current DFS path        boolean[] visited = new boolean[numCourses];                for (int i = 0; i < numCourses; i++) {            if (!dfs(i, adj, visited)) {                return false;            }        }                return true;    }        private boolean dfs(int course, List<List<Integer>> adj, boolean[] visited) {        if (visited[course]) {            return false; // Cycle detected        }        if (adj.get(course).isEmpty()) {            return true; // Already verified or no prerequisites        }                visited[course] = true;                for (int pre : adj.get(course)) {            if (!dfs(pre, adj, visited)) {                return false;            }        }                visited[course] = false; // Remove from current path        adj.get(course).clear(); // Mark as verified (optimization)                return true;    }}