207. Course Schedule

Intution

To determine if we can finish all courses, we need to detect if there's a cycle in the course dependency graph. Each course is a node, and each prerequisite is a directed edge.

• If there's a cycle, we get stuck in a loop of prerequisites — we cannot finish all courses.

• If there's no cycle, we can finish them all using some valid order.

Complexity

Space Complexity	Time Complexity
$\text{O}(N)$	$\text{O}(V*E)$

Code

// Helper function to detect cycle using DFS
boolean hasCycle(Map<Integer, List<Integer>> courseGraph, boolean[] visited, boolean[] inRecursion, int currentCourse) {

    // If this course is already in the current DFS path, a cycle is detected
    if (inRecursion[currentCourse]) return true;

    // If this course has already been processed and is safe, skip
    if (visited[currentCourse]) return false;

    // Mark the course as seen
    visited[currentCourse] = true;
    inRecursion[currentCourse] = true;

    // Check all courses that depend on the current course
    if (courseGraph.containsKey(currentCourse)) {
        for (int dependentCourse : courseGraph.get(currentCourse)) {
            if (hasCycle(courseGraph, visited, inRecursion, dependentCourse)) {
                return true;
            }
        }
    }

    // Backtrack: remove the course from current recursion path
    inRecursion[currentCourse] = false;

    return false;
}

public boolean canFinish(int totalCourses, int[][] prerequisites) {
    // Build the graph: key is a course, value is a list of courses that depend on it
    Map<Integer, List<Integer>> courseGraph = new HashMap<>();
    for (int[] pair : prerequisites) {
        int course = pair[0], prerequisite = pair[1];
        courseGraph.computeIfAbsent(prerequisite, k -> new ArrayList<>()).add(course);
    }

    boolean[] visited = new boolean[totalCourses];       // Tracks completed DFS
    boolean[] inRecursion = new boolean[totalCourses];   // Tracks current DFS path

    // Run DFS from each course to detect cycles
    for (int courseId = 0; courseId < totalCourses; ++courseId) {
        if (hasCycle(courseGraph, visited, inRecursion, courseId)) {
            return false; // Cycle detected
        }
    }

    return true; // No cycles found
}